从golang中的优先级队列中删除元素

Question

我从golang docs拿来了优先级队列的完整实现。我对一次删除几个元素很感兴趣，比如 heap.Remove(&queue, index1, index2, ...).

现在可以通过简单的方式完成：

for _, event := range events {
    heap.Remove(&queue, event.getIndex())
}

但是此方法有开销，因为每次调用 heap.Remove 都会重新组织树。如果我们可以先删除所有不需要的元素，然后再重新组织树，似乎效率更高。

如何实现？

Answer 1

为了回答这个问题，我们首先需要了解什么是堆。堆是一种数据结构，它允许我们根据它是最小堆还是最大堆来找到最大值或最小值。为了快速做到这一点，计算机维护了一棵树，这张图片总结得很好。这是最大堆：

当然计算机的内存不是按树状排列的，而是线性排列的。事实上，go 将堆存储在切片中，这意味着您可以像往常一样遍历切片并删除元素，例如：

  for i:=0; i<len(heap); i++ {  
    for _, element := heap {
      if element == to_remove {
        heap = append(heap[:i], heap[i+1:])
        i--
      }
    }
  }

Answer 2

由于堆的底层数据结构是一个切片，您可以直接从切片中删除元素，然后 re-initialize 再次从堆中移除。

从你的例子开始：

for _, event := range events {
    i := event.GetIndex()
    queue[i], queue[len(queue)-1] = queue[len(queue)-1], queue[i]
    queue = queue[:len(queue)-1]
}
heap.Init(&queue)

还有一个工作示例：https://play.golang.org/p/-KMEilCm3t9

func main() {
    h := IntHeap{1, 5, 2, 9, 8, 3, 7}

    toRemove := 8
    for i := 0; i < len(h); i++ {
        n := h[i]
        if n == toRemove {
            h[i], h[len(h)-1] = h[len(h)-1], h[i]
            h = h[:len(h)-1]
            i--
        }
    }

    heap.Init(&h)
    fmt.Println(h)
}

从golang中的优先级队列中删除元素

Remove elements from priority queue in golang

heap

priority-queue

go