algorithm - 为什么平衡 BST 没有在可变结构中普遍使用二叉堆？

Question

在我看来，二叉搜索树可以做二叉堆可以做的所有事情，还有一些额外的事情。

|                     |   Heap   | Bal. BST |
---------------------------------------------
| Lookup min element  |  O(1)    |  O(1)    |
---------------------------------------------
| Add an element      |  O(logn) |  O(logn) |
---------------------------------------------    
| Find and Remove     |  O(n)    |  O(logn) |
| an element          |          |          |
---------------------------------------------

作为查找和删除属性的结果，可以改变一个元素，我们几乎可以确保在 O(logn) 时间内改变后顺序仍然保持

我看到的二叉堆的优点是

i) 实现起来更简单ii) 分配的内存是连续的(因此访问速度更快)

(i) 不是问题，因为我很少会从头开始实现它们中的任何一个。如果我们经常改变元素，那么 (ii) 就不是一个显着的优势。

在我看来，平衡二叉树可以做二叉堆可以做的所有事情，那为什么它没有被普遍使用呢？ (就像双链表比单链表普遍使用一样)

Answer 1

一个更正，找到 BST 的最小值是 O(log(n))。堆具有比 BST 更好数字的其他区域。向堆中添加元素在实践中具有预期值 O(1)(平均为​​ 2 次比较)，这比 BST 更好。将列表变成堆的时间为 O(n)，这再次优于 BST 的 O(n log(n))。

最后，您将性能和连续内存都视为要求是错误的。堆通常用作实现优先级队列的一种方式，优先级队列通常用于性能关键代码段，如调度程序。举一个极端的例子，考虑操作系统内核中的调度程序。此外，一旦您进入内核，您习惯于交换内存和交换内存的抽象就会变得明确。因此，通常需要在内核代码中使用使用物理上连续内存的数据结构。这是堆的重大胜利。