堆与二叉搜索树(BST)

小开

Heap只保证较高级别的元素比较低级别的元素更大(对于max-heap)或更小(对于min-heap)，而BST保证顺序(从“左”到“右”)。如果你想要排序的元素，使用BST。

小开

二叉搜索树使用的定义是:对于每个节点，它左边的节点有一个更小的值(键)，而它右边的节点有一个更大的值(键)。

其中堆，作为二叉树的实现使用以下定义:

如果A和B是节点，其中B是A的子节点，则A的值(键)必须大于或等于B的值(键)，即: key(A)≥key(B).

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

我今天考试的时候也做了这道题，我答对了。微笑……：）

小开

什么时候使用堆，什么时候使用BST

Heap更擅长findMin/findMax (O(1))，而BST擅长所有 finds (O(logN))。Insert是这两个结构的O(logN)。如果你只关心findMin/findMax(例如，优先级相关)，使用heap。如果你想要一切都井然有序，那就用BST吧。

在这里的前几张幻灯片解释得很清楚。

小开

将数组中的所有n个元素插入BST需要O(nlogn)。一个数组中的n个元素可以在O(n)时间内插入到堆中。哪一个给堆带来了明显的优势

小开

正如其他人所提到的，Heap可以在O(1)中执行findMin 或 findMax，但不能在相同的数据结构中同时执行。然而，我不同意Heap在findMin/findMax中更好。事实上，稍微修改一下，BST就可以在O(1)中执行< em > < / em > findMin 而且 findMax。

在这个修改后的BST中，每次执行可能修改数据结构的操作时，都要跟踪最小节点和最大节点。例如，在插入操作中，您可以检查最小值是否大于新插入的值，然后将最小值分配给新添加的节点。同样的技术也可以应用在最大值上。因此，这个BST包含这些信息，您可以在O(1)中检索它们。(与二进制堆相同)

在这个BST(平衡BST)中，当你pop min或pop max时，下一个要分配的min值是min节点的的继任者，而下一个要分配的max值是max节点的前任。因此它在O(1)中执行。然而，我们需要重新平衡树，因此它仍然会运行O(log n)(与二叉堆相同)。

我很想在下面的评论中听到你的想法。谢谢:)

更新

交叉引用类似的问题我们可以用二叉搜索树来模拟堆操作吗?，以获得关于使用BST模拟堆的更多讨论。

小开

BST over Heap的另一种用法;因为有一个重要的区别:

在BST中找到后继和前任将花费O(h)时间。(O(logn) in balanced BST)
而在Heap中，则需要O(n)时间才能找到某个元素的后继或前任。

在堆上使用BST:现在，让我们说我们使用一个数据结构来存储航班的着陆时间。如果着陆时间差值小于“d”，我们不能安排航班降落。并且假设许多航班已经安排在一个数据结构(BST或Heap)中降落。

现在，我们想要安排另一个将降落在t的航班。因此，我们需要计算t与它的继任者和前任(应该是>d)的差异。因此，我们将为此需要一个BST，如果平衡，它将在O(logn)中快速即。

编辑:

排序 BST需要O(n)时间按顺序打印元素(内序遍历)，而Heap可以在O(n logn)时间内完成。 Heap提取最小元素并重新堆化数组，这使得它在O(n logn)时间内完成排序

小开

总结

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)

除Insert外，该表上的所有平均时间都与最差时间相同。

*:在这个答案的任何地方，BST ==平衡BST，因为不平衡是渐进的

**:使用一个简单的修改解释在这个答案

***: log(n)为指针树堆，n为动态数组堆

二进制堆相对于BST的优势

插入二进制堆的平均时间为O(1)，因为BST为O(log(n))。这是堆的杀手特性。

还有其他的堆达到O(1)的平摊(更强)，比如斐波那契堆，甚至最坏的情况，比如Brodal队列，尽管由于非渐近性能，它们可能不实用:斐波那契堆或布罗达队列在实践中使用吗?

二进制堆可以有效地在动态数组或基于指针的树的顶部实现，BST只能基于指针的树。因此对于堆，我们可以选择更节省空间的数组实现，如果我们可以承受偶尔的调整大小延迟。

二进制堆创建O(n)是最坏的情况吗， O(n log(n))为BST。

BST相对于二进制堆的优势

搜索任意元素是O(log(n))。这是bst的杀手特性。

对于堆，它一般是O(n)，除了最大的元素是O(1)。

“False"堆相对于BST的优势

堆是O(1)找到max, BST O(log(n))。

这是一种常见的误解，因为修改BST以跟踪最大的元素并在该元素可能更改时更新它是很简单的:插入较大的交换，删除时查找第二大的交换。我们可以用二叉搜索树来模拟堆操作吗?(提到了由杨)。

实际上，与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

直观的论点:

树的底层比顶层有指数级的元素，所以新元素几乎肯定会出现在底层

堆插入从底层开始, BST必须从顶部开始

在二进制堆中，由于相同的原因，增加给定索引处的值也是O(1)。但如果你想这样做，你可能会想要在堆操作如何实现O(logn)减键操作基于最小堆优先级队列?上保持一个额外的最新索引，例如Dijkstra。不需要额外的时间成本。

GCC c++标准库在实际硬件上插入基准

我对c++的std::set (红黑树BST)和std::priority_queue (动态数组堆)插入进行基准测试，看看我对插入时间的判断是否正确，这就是我得到的结果:

基准代码

剧情脚本 .

plot data

在联想ThinkPad P51笔记本电脑上测试Ubuntu 19.04, GCC 8.3.0, CPU:英特尔酷睿i7-7820HQ CPU(4核/ 8线程，2.90 GHz基数，8 MB缓存)，RAM: 2倍三星M471A2K43BB1-CRC(2倍16GiB, 2400 Mbps)， SSD:三星MZVLB512HAJQ-000L7 (512GB, 3000 MB/s)

所以很明显:

堆插入时间基本不变。

我们可以清楚地看到动态数组调整大小的点。由于我们平均每10k个插入能够看到任何高于系统噪声的东西，这些峰值实际上比显示的要大10k倍!

放大后的图基本上只排除了数组大小调整点，并显示几乎所有插入都在25纳秒以内。

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

BST vs hashmap详细分析:在c++中std::map内部是什么数据结构?

GCC c++标准库在gem5上插入基准

gem5是一个完整的系统模拟器，因此使用m5 dumpstats提供了一个无限精确的时钟。因此，我尝试使用它来估计单个插入的时间。

解释:

heap仍然是常量，但现在我们更详细地看到有几行，每一行越高越稀疏。

这必须对应于内存访问延迟是为越来越高的插入。

我真的不能完全解释BST，因为它看起来不那么对数，有点更常数。

有了这个更大的细节，我们可以看到也可以看到一些不同的线条，但我不确定它们代表什么:我希望底线更细，因为我们插入上下?

在aarch64 HPI CPU上使用此Buildroot设置进行基准测试。

BST不能有效地在数组上实现

堆操作只需要向上或向下冒泡一个树枝，所以O(log(n))最差情况互换，O(1)平均。

保持BST平衡需要树旋转，这可以改变顶部的元素为另一个，并需要移动整个数组(O(n))。

堆可以有效地在数组上实现

父索引和子索引可以从当前索引如图所示计算。

没有像BST那样的平衡操作。

删除最小值是最令人担忧的操作，因为它必须是自顶向下的。但这总是可以通过“向下渗透”来实现的。堆的一个分支正如这里所解释的。这将导致O(log(n))最坏的情况，因为堆总是很好地平衡。

如果您每删除一个节点就插入一个节点，那么您就失去了堆提供的渐近O(1)平均插入的优势，因为删除将占主导地位，并且您还可以使用BST。然而，Dijkstra每次删除节点都会更新几次，所以我们没有问题。

动态数组堆与指针树堆

堆可以有效地在指针堆上实现:有可能使高效的基于指针的二进制堆实现吗?

动态数组实现的空间利用率更高。假设每个堆元素只包含一个指向struct的指针:

树的实现必须为每个元素存储三个指针:父元素、左子元素和右子元素。所以内存使用总是4n(3个树指针+ 1个struct指针)。

树bst还需要进一步的平衡信息，例如黑-红。

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

另一方面，树堆有更好的最坏情况插入，因为复制后台动态数组以使其大小翻倍需要O(n)最坏情况，而树堆只是为每个节点进行新的小分配。

不过，备份数组加倍是O(1)平摊的，所以它归结为最大延迟考虑。这里提到。

哲学

bst维护父节点和所有子节点之间的全局属性(左小，右大)。

BST的顶部节点是中间元素，它需要全局知识来维护(知道有多少更小和更大的元素)。

这个全局属性的维护成本更高(log n insert)，但提供了更强大的搜索(log n search)。

堆在父级和直接子级之间维护一个本地属性(parent >孩子)。

堆的顶部节点是大元素，它只需要本地知识来维护(知道父元素)。

比较BST、Heap和Hashmap:

BST:可以是一个合理的:

无序集(确定元素之前是否插入的结构)。但是由于O(1)平摊插入，hashmap倾向于更好。

分类机。但是堆通常在这方面做得更好，这就是为什么堆排序比树的种类更广为人知的原因

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

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

双链接列表

双链表可以被视为堆的子集，其中第一项优先级最高，所以让我们在这里比较它们:

<李>插入:
<李>位置:

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

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

<李>时间:

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

二进制堆:O(1)平均，因此不如链表。有更一般的插入位置的折衷。

搜索:O(n)

这样做的一个用例是当堆的键是当前时间戳时:在这种情况下，新条目总是会到列表的开头。所以我们甚至可以完全忘记确切的时间戳，只保留列表中的位置作为优先级。

这可以用来实现LRU缓存。就像用于堆应用程序，如Dijkstra一样，你需要保留一个从键到列表中相应节点的额外哈希映射，以查找要快速更新的节点。

不同平衡BST的比较

虽然渐近插入和查找时间的所有数据结构，通常被分类为“平衡bst"到目前为止我所看到的是一样的，不同的bbst确实有不同的权衡。我还没有完全研究这个问题，但在这里总结一下这些权衡是很好的:

红黑树。似乎是2019年最常用的BBST，例如GCC 8.3.0 c++实现使用的BBST

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

WAVL。原始论文提到了该版本在重新平衡和旋转操作边界方面的优势。

另请参阅

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

小开

堆是实现优先级队列的具体数据结构。

没有理由保持分支因子固定等于2。一般来说，我们可以有d-ary树:

用于堆的树是完整树。创建堆是为了获取数据中优先级最高的元素。然而二分搜索作为

堆不适用于检查是否有元素存储在其中。你别无选择，只能经历所有的元素，直到你找到你要找的，或者我们进入数组的结束。这意味着一个线性时间算法。它是 O(log(n))用于二叉搜索树

二叉搜索树不允许重复，但是堆允许。

二叉搜索树是有序的，堆不是有序的。

在堆中插入和删除将花费O(log(n))时间。在二叉搜索树中，这可能需要O(n)时间，如果树是完整的不平衡的。在下图中，你可以看到两个bst，右边的一个是链式的所以插入和删除可能需要O(N)，但对于左边的O(Log(N))

堆可以在线性时间内构建(使用heapify)，然而，BST需要O(n * log(n))来创建。

堆是完全树。这是非常重要的事实。因为当你插入的时候你必须从最后一个插入，这样交换之后会有完整的树形结构。类似地，当你删除时，删除从根开始，先删除根再保留完整的树结构中最后一个元素应该是树

参考