如何从二进制堆中删除元素？ [英] How to remove elements from a binary heap?

问题描述

据了解，二进制堆不支持删除随机元素。如果我需要从二进制堆中删除​​随机元素？

显然，我可以删除一个元素在 O（N）中整理堆。我可以做得更好吗

解决方案

是和否。

问题是二进制堆不支持搜索的任意元素。发现它本身是 O（n）。

但是，如果你有一个指向元素的指针只有它的值） - 你可以用最右边的叶片交换元素，删除这个叶子，而不是重新堆叠相关的子堆（通过根据需要筛选新放置的元素）。这导致 O（logn）删除，但需要指向您要查找的实际元素的指针。

As I understand, binary heap does not support removing random elements. What if I need to remove random elements from a binary heap?

Obviously, I can remove an element and re-arrange the entire heap in O(N). Can I do better?

解决方案

Yes and no.

The problem is a binary heap does not support search for an arbitrary element. Finding it is itself O(n).

However, if you have a pointer to the element (and not only its value) - you can swap the element with the rightest leaf, remove this leaf, and than re-heapify the relevant sub-heap (by sifting down the newly placed element as much as needed). This results in O(logn) removal, but requires a pointer to the actual element you are looking for.

这篇关于如何从二进制堆中删除元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！