据我了解，binary heap不支持删除随机元素。如果我需要从 a 中删除随机元素binary heap怎么办？
显然，我可以删除一个元素并将整个堆重新排列在O(N). 我能做得更好吗？
问问题
14290 次
3 回答
23
是和不是。
问题是二叉堆不支持搜索任意元素。寻找它本身O(n)。
但是，如果你有一个指向元素的指针（而不仅仅是它的值） -你可以用最右边的叶子交换元素，删除这个叶子，然后重新堆化相关的子堆（通过筛选新放置的元素尽可能多）。这会导致O(logn)删除，但需要指向您正在寻找的实际元素的指针。
于 2012-09-02T06:10:29.817 回答
8
阿米特的回答是正确的，但这里还有一个细微差别：
可能需要将已删除项目的位置（放置最右边的叶子的位置）冒泡（与父级比较并向上移动直到父级大于您）。有时需要向下冒泡（与孩子比较并向下移动，直到所有孩子都比你小）。这一切都取决于具体情况。
于 2014-02-22T01:47:34.863 回答
3
取决于“随机元素”的含义。如果这意味着堆包含元素 [e1, e2, ..., eN] 并且想要删除一些 ei (1 <= i <= N)，那么这是可能的。
如果您使用某个库中的二进制堆实现，则可能是它没有为您提供所需的 API。在这种情况下，您应该寻找另一个拥有它的库。
如果您要自己实现它，则需要两个额外的调用：
A procedure deleteAtIndex(heap, i) that deletes the node at index i by positioning the last element in the heap array at i, decrementing the element count, and finally shuffling down/up the new ith element to maintain the heap invariant. The most common use of this procedure is to "pop" the heap by calling deleteAtIndex(heap, 1) -- assuming 1-origin indexing. This operation will run O(log n) (though, to be complete, I'll note that the highest bound can be improved up to O(log(log n)) depending on some assumptions about your elements' keys).
A procedure deleteElement(heap, e) that deletes the element e (your arbitrary element). Your heap algorithm would maintain an array ElementIndex such that ElementIndex[e] returns the current index of element e: calling deleteAtIndex(heap, ElementIndex[e]) will then do what you want. It will also run in O(log n) because the array access is constant.
Since binary heaps are often used in algorithms that merely pop the highest (or lowest) priority element (rather than deleting arbitrary elements), I imagine that some libraries might miss on the deleteAtIndex API to save space (the extra ElementIndex array mentioned above).
于 2014-05-23T21:05:16.827 回答