如何从二进制堆中删除元素？

Question

据我了解,binary heap不支持删除随机元素.如果我需要删除a中的随机元素binary heap怎么办？

显然,我可以删除一个元素并重新安排整个堆O(N).我可以做得更好吗？

Answer 1

是的,不是.

问题是二进制堆不支持搜索任意元素.找到它本身O(n).

但是,如果你有一个指向元素的指针(而不仅仅是它的值) - 你可以用最右边的叶子交换元素,删除这个叶子,然后重新堆积相关的子堆(通过筛选新放置的元素)尽可能多的).这会导致O(logn)删除,但需要指向您要查找的实际元素的指针.

Answer 2

阿米特的答案是正确的,但这里还有一个细微差别:

可以要求将已移除项目的位置(放置最右侧叶子的位置)冒泡(与父项比较并向上移动直到父项大于您).有时需要泡下来(与孩子比较并向下移动,直到所有孩子都比你小).这一切都取决于具体情况.