algorithm - 堆与二叉搜索树 (BST)

Question

堆和 BST 有什么区别？

何时使用堆，何时使用 BST？

如果你想以排序的方式获取元素，BST 比堆更好吗？

Answer 1

摘要

          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

除了插入之外，该表上的所有平均时间都与其最坏时间相同。

* :在这个答案中的所有地方，BST == 平衡 BST，因为不平衡逐渐吸吮

** :使用此答案中解释的微不足道的修改

*** :log(n)对于指针树堆，n用于动态数组堆

二叉堆相对于 BST 的优势

插入二进制堆的平均时间为 O(1) , 对于 BST 是 O(log(n)) . 此 是堆的杀手锏。
还有其他堆到达 O(1)摊销(更强)像 Fibonacci Heap ，甚至最坏的情况，如 Brodal queue ，尽管由于非渐近性能，它们可能不实用:Are Fibonacci heaps or Brodal queues used in practice anywhere?

二叉堆可以在 dynamic arrays 上有效地实现或基于指针的树，BST 仅基于指针的树。所以对于堆，如果我们能承受偶尔调整大小的延迟，我们可以选择空间效率更高的数组实现。

二叉堆创建is O(n) worst case , O(n log(n))对于 BST。

BST 相对于二叉堆的优势

搜索任意元素是 O(log(n)) . 此 是 BST 的杀手锏。
对于堆，它是 O(n)一般来说，除了最大的元素是 O(1) .

堆相对于 BST 的“虚假”优势

堆是 O(1)找到最大值，BST O(log(n)) .
这是一个常见的误解，因为修改 BST 以跟踪最大元素并在该元素可以更改时更新它是微不足道的:插入较大的交换时，删除时找到第二大元素。 Can we use binary search tree to simulate heap operation? (提到 by Yeo )。
实际上，与 BST 相比，这是堆的一个限制:唯一有效的搜索是针对最大元素的搜索。

平均二进制堆插入为 O(1)
资料来源:

纸:http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf

WSU 幻灯片:- WSU 幻灯片:https://web.archive.org/web/20161109132222/http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

直观论证:

底部树级别的元素比顶部级别多，因此新元素几乎肯定会在底部

堆插入starts from the bottom , BST 必须从顶部开始

在二叉堆中，增加给定索引处的值也是 O(1)出于同样的原因。但是如果你想这样做，你很可能希望在堆操作中保持一个额外的索引是最新的 How to implement O(logn) decrease-key operation for min-heap based Priority Queue?例如对于迪杰斯特拉。无需额外的时间成本即可实现。
GCC C++ 标准库在真实硬件上插入基准测试
我对 C++ 进行了基准测试 std::set ( Red-black tree BST ) 和 std::priority_queue ( dynamic array heap ) 插入看看我对插入时间是否正确，这就是我得到的:

benchmark code

plot script

plot data

在 Ubuntu 19.04、GCC 8.3.0 的 Lenovo ThinkPad P51 笔记本电脑上测试，CPU:Intel Core i7-7820HQ CPU(4 核/8 线程，2.90 GHz 基础，8 MB 缓存)，RAM:2x Samsung M471A2K43BB1-CRC(2x 16GiB , 2400 Mbps), SSD: 三星 MZVLB512HAJQ-000L7 (512GB, 3,000 MB/s)

这么清楚:

堆插入时间基本不变。
我们可以清楚地看到动态数组大小调整点。因为我们平均每 10k 次插入 to be able to see anything at all above system noise ，这些峰值实际上比显示的大约大 10k 倍!
缩放图基本上只排除了阵列大小调整点，并显示几乎所有插入都低于 25 纳秒。

BST 是对数的。所有插入都比平均堆插入慢得多。

BST vs hashmap 详分割析在:What data structure is inside std::map in C++?

GCC C++ 标准库在 gem5 上插入基准测试
gem5是一个完整的系统模拟器，因此提供了无限精确的时钟与 m5 dumpstats .所以我尝试用它来估计单个插入的时间。

解释:

heap 仍然是不变的，但现在我们更详细地看到有几行，每行越高，越稀疏。
这必须对应于为越来越高的插入完成的内存访问延迟。

TODO 我无法真正完整地解释 BST，因为它看起来不像对数而且更恒定。
然而，有了这个更详细的信息，我们也可以看到一些不同的线条，但我不确定它们代表什么:我希望底线更细，因为我们插入了顶部底部？

以此为基准 Buildroot setup在 aarch64 上 HPI CPU .
BST 无法在阵列上有效实现
堆操作只需要向上或向下冒泡单个 Twig ，所以 O(log(n))最坏情况掉期， O(1)平均。
保持 BST 平衡需要树旋转，这可以将顶部元素更改为另一个，并且需要移动整个数组( O(n) )。
堆可以有效地在数组上实现
可以从当前索引 as shown here 计算父索引和子索引.
没有像 BST 那样的平衡操作。
Delete min 是最令人担忧的操作，因为它必须是自上而下的。但是它总是可以通过“渗透”堆的单个分支来完成 as explained here .这导致 O(log(n)) 最坏的情况，因为堆总是很好地平衡。
如果您为删除的每个节点插入一个节点，那么您将失去堆提供的渐近 O(1) 平均插入的优势，因为删除将占主导地位，您不妨使用 BST。然而，Dijkstra 每次删除都会多次更新节点，所以我们很好。
动态数组堆与指针树堆
堆可以在指针堆之上有效地实现: Is it possible to make efficient pointer-based binary heap implementations?
动态数组实现的空间效率更高。假设每个堆元素只包含一个指向 struct 的指针。 :

树实现必须为每个元素存储三个指针:父、左子和右子。所以内存使用总是4n (3 个树指针 + 1 struct 指针)。
树 BST 还需要进一步的平衡信息，例如黑红色。

动态数组实现的大小可以是 2n加倍之后。所以平均而言，它将是 1.5n .

另一方面，树堆有更好的最坏情况插入，因为复制后备动态数组使其大小加倍需要 O(n)最坏的情况，而树堆只是为每个节点进行新的小分配。
尽管如此，后备阵列加倍是 O(1)摊销，因此归结为最大延迟考虑。 Mentioned here .
经营理念

BST 在父级和所有后代(左小，右大)之间维护一个全局属性。
BST 的顶部节点是中间元素，它需要全局知识来维护(知道有多少较小和较大的元素)。
这个全局属性的维护成本更高(log n insert)，但提供了更强大的搜索(log n search)。

堆在父级和直接子级(父级 > 子级)之间维护本地属性。
堆的顶部节点是大元素，它只需要维护本地知识(知道你的父节点)。

比较 BST 与堆与 Hashmap:

BST:可以是合理的:

无序集(一种确定元素之前是否插入过的结构)。但是由于 O(1) 分摊插入，hashmap 往往会更好。

分拣机。但是堆通常在这方面做得更好，这就是为什么 heapsort比tree sort更广为人知

heap:只是一个排序机器。不能是有效的无序集合，因为您只能快速检查最小/最大元素。

哈希映射:只能是一个无序的集合，而不是一个高效的排序机器，因为哈希混淆了任何排序。

双向链表
双向链表可以看作是堆的子集，其中第一项具有最高优先级，因此我们也在这里比较它们:

插入:

位置:

双向链表:插入的项必须是第一个或最后一个，因为我们只有指向这些元素的指针(除非我们有指向感兴趣位置的指针，例如在迭代期间)

二叉堆:插入的项目可以在任何位置结束。比链表限制更少。

时间:

双向链表:O(1)最坏的情况，因为我们有指向项目的指针，更新非常简单

二叉堆:O(1)平均，因此比链表差。权衡具有更一般的插入位置。

搜索:O(n)对于两者

一个用例是当堆的键是当前时间戳时:在这种情况下，新条目将始终位于列表的开头。所以我们甚至可以完全忘记确切的时间戳，只保留列表中的位置作为优先级。
这可用于实现 LRU cache .就像 for heap applications like Dijkstra ，您将需要保留一个从键到列表对应节点的附加哈希图，以快速找到要更新的节点。
不同平衡BST的比较
尽管到目前为止我看到的所有通常归类为“平衡 BST”的数据结构的渐近插入和查找时间是相同的，但不同的 BBST 确实有不同的权衡。我还没有完全研究过这个，但最好在这里总结一下这些权衡:

Red-black tree .似乎是 2019 年最常用的 BBST，例如它是 GCC 8.3.0 C++ 实现使用的一个

AVL tree .似乎比 BST 更平衡，因此它可能会更好地查找延迟，但代价是查找成本稍高。 Wiki 总结道:“AVL 树经常与红黑树进行比较，因为两者都支持相同的操作集并且在基本操作上花费 [相同的] 时间。对于查找密集型应用程序，AVL 树比红黑树更快，因为它们更严格平衡。与红黑树类似，AVL 树是高度平衡的。一般来说，对于任何 mu < 1/2，两者都不是权重平衡的，也不是 mu 平衡的；也就是说，兄弟节点可以有很大的不同数量的后代。”

WAVL . original paper提到了该版本在重新平衡和旋转操作的界限方面的优势。

另见
CS上的类似问题: https://cs.stackexchange.com/questions/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap