algorithm - 向堆添加和删除值的高效算法

Question

如果我想在最大堆中添加和删除值，我会首先将值添加到堆的末尾，然后根据需要向上渗透。然后我会通过保存根节点来删除该值，然后在最大堆的末尾取值，将其移动到顶部，然后根据需要向下渗透，最后返回从前面保存的值。

这涉及大量的比较和值交换。是否有一种算法具有类似的复杂度类但对于首先添加然后删除最大堆中的值更有效？

Answer 1

添加到二进制堆需要 log(N) 比较。移除一个项目，假设你知道项目在哪里，需要 log(N) 比较。从堆中删除的低效部分是找到要删除的项目。这需要 O(N) 时间。

顺便说一句，您可以通过获取堆中的最后一项，将其放在要删除的项的位置，然后根据需要向上或向下渗透来提高删除性能。有关示例，请参见任何算法文本。

如果你想要一个更高效的数据结构，你需要一个二进制堆以外的东西。