堆与二进制搜索树（BST）

问题描述 投票：138回答：8

堆和BST有什么区别？

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

如果你想以排序的方式获取元素，BST是否优于堆？

algorithm binary-tree heap binary-search-tree
8个回答
154
投票

摘要

          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 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)

资料来源：

直观的论点：

  • 底层树的元素比顶层有更多的元素，所以新元素几乎肯定会在底部
  • 堆插入starts from the bottom，BST必须从顶部开始

在二进制堆中，出于同样的原因，增加给定索引处的值也是O(1)。但是如果你想这样做，很可能你会想要在堆操作How to implement O(logn) decrease-key operation for min-heap based Priority Queue?上保持最新的索引是最新的，例如：为Dijkstra。可能没有额外的时间成本。

GCC C ++标准库在真实硬件上插入基准

我对C ++ std::set（Red-black tree BST）和std::priority_queue（dynamic array heap）插入进行了基准测试，看看我是否对插入时间是正确的，这就是我得到的：

enter image description here

  • benchmark code
  • plot script
  • plot data
  • 在联想ThinkPad P51笔记本电脑的Ubuntu 19.04，GCC 8.3.0上测试，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）

很明显：

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

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

enter image description here

解释：

  • 堆仍然是常量，但现在我们更详细地看到有几行，每一个更高的行更稀疏。 这必须对应于更高和更高插入的内存访问延迟。
  • TODO我不能完全解释BST，因为它看起来不那么对数而且更加稳定。 有了这个更详细的细节，我们可以看到也可以看到一些不同的线条，但我不确定它们代表什么：我希望底线更薄，因为我们插入顶部底部？

在aarch64 Buildroot setup上用这个HPI CPU进行基准测试。

BST不能在阵列上有效实现

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

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

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

可以从当前索引as shown here计算父和子索引。

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

删除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）。
  • 堆在父级和直接子级（父级>子级）之间维护本地属性。 堆的前调是大元素，只需要本地知识来维护（知道你的父级）。

双链表

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

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

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

这可以用来实现LRU cache。就像for heap applications like Dijkstra一样，您将希望从密钥到列表的相应节点保留一个额外的散列映射，以找到要快速更新的节点。

也可以看看

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

70
投票

堆只是保证较高级别的元素（对于最大堆）或较小（对于最小堆）比较低级别的元素更大，而BST保证顺序（从“左”到“右”）。如果您想要排序元素，请使用BST。

47
投票

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

堆在findMin / findMax（O(1)）更好，而BST在所有发现（O(logN)）都很好。插入是两个结构的O(logN)。如果您只关心findMin / findMax（例如与优先级相关），请使用堆。如果您想要对所有内容进行排序，请使用BST。

来自here的前几张幻灯片非常清楚地解释了事情。

7
投票

正如其他人所提到的，Heap可以在O（1）中执行findMin或findMax，但不能在相同的数据结构中执行。但是我不同意Heap在findMin / findMax中更好。事实上，经过略微修改，BST可以在O（1）中同时执行findMin和findMax。

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

在此BST（平衡BST）中，当您使用pop min或pop max时，要分配的下一个最小值是最小节点的后继，而要分配的下一个最大值是最大节点的前一个。因此它在O（1）中执行。但是我们需要重新平衡树，因此它仍然会运行O（log n）。 （与二进制堆相同）

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

更新

交叉引用类似问题Can we use binary search tree to simulate heap operation?有关使用BST模拟Heap的更多讨论。

3
投票

二叉搜索树使用以下定义：对于每个节点，其左侧的节点具有较小的值（键），而右侧的节点具有较大的值（键）。

作为堆的位置，作为二叉树的实现使用以下定义：

如果A和B是节点，其中B是A的子节点，那么A的值（key）必须大于或等于B的值（key）。即，key（A）≥key（B） ）。

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

今天我为同一个问题跑了同样的问题，我做对了。微笑...... :)

3
投票

BST在堆上的另一种用途;因为一个重要的区别：

  • 在BST中寻找继任者和前任将花费O（h）时间。 （平衡BST中的O（logn））
  • 在Heap中，花费O（n）时间来寻找某个元素的继承者或前身。

在堆上使用BST：现在，让我们说我们使用数据结构来存储航班的着陆时间。如果着陆时间的差异小于“d”，我们就无法安排降落。并假设已安排许多航班降落在数据结构（BST或堆）中。

现在，我们想安排另一架将降落的航班。因此，我们需要计算t与其后继者和前身的差异（应该> d）。因此，我们需要一个BST，它可以快速进行，如果平衡则在O（logn）。

编辑：

排序BST需要O（n）时间来按排序顺序打印元素（Inorder遍历），而Heap可以在O（n logn）时间内完成。堆提取min元素并重新堆积数组，这使得它在O（n logn）时间内进行排序。

1
投票

将数组中的所有n个元素插入BST需要O（n logn）。数组中的n个元素可以在O（n）时间内插入堆中。这给了堆一个明确的优势

0
投票

堆只是保证较高级别的元素比较低级别的元素更大（对于最大堆）或更小（对于最小堆）

我喜欢上面的答案，并且我的评论更具体地针对我的需求和用法。我必须得到n个位置列表找到从每个位置到特定点的距离说（0,0），然后返回距离较小的m个位置。我使用的是优先队列，即堆。为了找到距离并放入堆中，每次插入都需要n（log（n））n个位置log（n）。然后，为了获得具有最短距离的m，需要m（log（n））m个位置log（n）删除堆积。

如果我不得不用BST这样做，它会花费我n（n）最坏情况插入。（假设第一个值非常小，所有其他值依次越来越长，树只跨越右子或左子如果越来越小。分钟将花费O（1）时间，但我必须平衡。所以从我的情况和所有上述答案我得到的是当你只是在最低或最高优先级的基础上去的时候去为堆。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.