堆与二进制搜索树(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)

除了Insert之外,此表中的所有平均时间与其最差时间相同.

• *:在这个答案的每个地方,BST ==平衡的BST,因为不平衡会渐渐变得糟透了
• **:使用这个答案中解释的微不足道的修改
• ***:log(n)用于指针树堆,n用于动态数组堆

二进制堆相对于BST的优点

• O(1)对于BST来说,插入二进制堆的平均时间是O(log(n)).这是堆的杀手特征.

  还有其他堆O(1)像斐波纳契堆一样达到摊销(更强),甚至最坏的情况,如布罗达尔队列,虽然由于非渐近性能而可能不实用:Fibonacci堆或Brodal队列在实践中用于何处？

• 二进制堆可以在动态数组或基于指针的树之上有效地实现,BST仅基于指针的树.因此,对于堆,我们可以选择更节省空间的阵列实现,如果我们能够承受偶尔的调整大小延迟.

• 对于BST ,二进制堆创建是O(n)最坏的情况O(n log(n)).

BST优于二进制堆的优势

• 搜索任意元素是O(log(n)).这是BST的杀手级功能.

  对于堆,它O(n)通常是,除了最大的元素O(1).

堆超过BST的"假"优势

• 堆是O(1)找到最大值,BST O(log(n)).

  这是一个常见的误解,因为修改BST以跟踪最大元素并在每次更改元素时更新它是微不足道的:插入较大的一个交换时,在删除时找到第二大元素.我们可以使用二叉搜索树来模拟堆操作吗？(Yeo提到).

  实际上,与BST相比,这是堆的限制:唯一有效的搜索是对于最大元素.

平均二进制堆插入是 O(1)

资料来源:

• 论文:http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• WSU幻灯片: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(动态数组堆)插入进行基准测试,以查看我是否对插入时间是正确的,这就是我得到的:

很明显:

• 堆插入时间基本上是不变的.

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

  缩放图基本上只排除了数组调整大小点,并显示几乎所有插入都落在25纳秒以下.

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

Ubuntu 18.04,GCC 7.3,Intel i7-7820HQ CPU,DDR4 2400 MHz RAM,联想Thinkpad P51.

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

gem5是一个完整的系统模拟器,因此提供了一个无限精确的时钟m5 dumpstats.所以我试着用它来估算单个插入的时间.

解释:

• 堆仍然是常量,但现在我们更详细地看到有几行,每一个更高的行更稀疏.

  这必须对应于更高和更高插入的内存访问延迟.

• TODO我不能完全解释BST,因为它看起来不那么对数而且更加稳定.

  有了这个更详细的细节,我们可以看到也可以看到一些不同的线条,但我不确定它们代表什么:我希望底线更薄,因为我们插入顶部底部？

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

BST不能在阵列上有效实现

堆操作只需要向上或向下冒泡一个树分支,因此O(log(n))最坏情况下交换O(1)平均值.

保持BST平衡需要树旋转,这可以将顶部元素更改为另一个,并且需要围绕(O(n))移动整个阵列.

堆可以在阵列上有效地实现

可以从当前索引计算父子索引,如此处所示.

没有像BST这样的平衡操作.

删除min是最令人担忧的操作,因为它必须自上而下.但它总是可以通过"向下渗透"堆单支做如下解释.这导致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).

• 堆在父级和直接子级(父级>子级)之间维护本地属性.

  堆的前调是大元素,只需要本地知识来维护(知道你的父级).

双链表

双链表可以看作堆的子集,其中第一个项具有最高优先级,所以我们在这里比较它们:

• 插入:
  • 位置:
    • 双向链表:插入的项必须是第一个或最后一个,因为我们只有指向这些元素的指针.
    • 二进制堆:插入的项目可以在任何位置结束.比链表更少限制.
  • 时间:
    • 双链表:O(1)最糟糕的情况,因为我们有指向项目的指针,而且更新非常简单
    • 二进制堆:O(1)平均值,因此比链表更差.具有更一般插入位置的权衡.
• 搜索:O(n)两者兼而有之

一个用例是当堆的密钥是当前时间戳时:在这种情况下,新条目将始终到达列表的开头.所以我们甚至可以完全忘记确切的时间戳,只需将列表中的位置作为优先级.

这可用于实现LRU缓存.就像Dijkstra这样的堆应用程序一样,您需要将一个额外的hashmap从密钥保留到列表的相应节点,以找到要快速更新的节点.

BST vs Hash地图

详细分析:在C++中std :: map里面有什么数据结构？

这是一个预览:

也可以看看

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

Answer 2

堆只是保证较高级别的元素(对于最大堆)或较小(对于最小堆)比较低级别的元素更大,而BST保证顺序(从"左"到"右").如果您想要排序元素,请使用BST.

Answer 3

何时使用堆以及何时使用BST

Heap在findMin/findMax(O(1))方面更好,而BST在所有 finds(O(logN))方面都很出色.插入适用O(logN)于两种结构.如果您只关心findMin/findMax(例如与优先级相关),请使用堆.如果您想要对所有内容进行排序,请使用BST.

这里的前几张幻灯片非常清楚地解释了事情.

Answer 4

如其他人提及的,堆可以做findMin 或 findMax在O(1)但不能同时在相同的数据结构.但是我不同意Heap在findMin/findMax中更好.事实上,有轻微的变形例中,BST可以做既 findMin 和 findMax在O(1).

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

在该BST(平衡BST),当你pop min或pop max,要分配的下一分钟值是后继最小节点的,而要分配的下一最大值是前身最大的节点.因此它在O(1)中执行.但是我们需要重新平衡树,因此它仍然会运行O(log n).(与二进制堆相同)

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

更新

对类似问题的交叉引用我们可以使用二叉搜索树来模拟堆操作吗？有关使用BST模拟堆的更多讨论.