堆与二进制search树（BST）

堆和BST有什么区别？

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

如果你想以sorting的方式获取元素，BST是否比堆更好？

Answer 1

概要

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

* ：使用在这个答案中解释的微不足道的修改。

二进制堆比平衡BST的优势

• 平均时间插入二进制堆是O(1) ，对于BST是O(log(n)) 。 这是堆的杀手function。

  还有其他一些像Fibonacci Heap那样到达O(1)摊销（更强）的堆 ，甚至是最坏的情况，就像Brodal队列一样 ，尽pipe由于非渐近性能，它们可能并不实用： 是Fibonacci堆还是Brodal队在任何地方实践？

• 二进制堆可以有效地实现在数组之上，BST不能。

  所以我们不必为每个节点（左边，右边，父节点）存储3个指针，加上平衡数据（比如RB-ness），以一个常数来保存内存。

• 对于BST，二进制堆的创build是O(n)最坏的情况 ， O(n log(n)) 。

BST优于二进制堆

• search任意元素是O(log(n)) 。 这是BST的杀手锏。

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

堆“BST”的“假”优势

• 堆是O(1)find最大值，BST O(log(n)) 。

  这是一个常见的误解，因为修改一个平衡的BST以跟踪最大的元素是微不足道的，并且每当元素可以改变时更新它：插入一个较大的交换，在去除中find第二大。 我们可以使用二叉search树来模拟堆操作吗？ （ 由Yeo提到）。

  实际上，与BST相比，这是一个堆的限制 ： 唯一有效的search就是最大的元素。

平均二进制堆插入是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）减less键操作？ 例如Dijikstra。 可能没有额外的时间成本。

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

堆操作只需要在单个树分支上冒泡，所以O(log(n))最差情况交换， O(1)平均值。

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

哲学

• BST在父母和所有后代之间保持全球财产（左小，右大）。

  平衡BST的顶级节点是中间元素，需要全局知识来维护（知道有多less更小的元素）。

  这个全局属性维护成本更高（log n insert），但是提供了更强大的search（log n search）。

• 家庭和直接孩子（家长和孩子）之间的堆保持本地财产。

  堆的最前面是大元素，只需要本地知识来维护（知道你的父母）。

双链表

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

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

一个用例就是当堆的关键字是当前时间戳时：在这种情况下，新的入口总是会到达列表的开始处。 所以我们甚至可以完全忘记确切的时间戳，只要保持列表中的位置为优先。

这可以用来实现一个LRUcaching 。 就像Dijkstra这样的堆应用程序一样 ，您需要保留从密钥到列表中相应节点的附加散列表，以便快速find要更新的节点。

也可以看看

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

findMin / findMax（ O(1) ）堆是更好的，而BST在所有发现（ O(logN) ）都很好。 两个结构的插入都是O(logN) 。 如果你只关心findMin / findMax（例如与优先级相关的），那就去堆。 如果你想要一切sorting，使用BST。

从这里开始的几张幻灯片很清楚地解释了事情。

Answer 4

正如其他人所提到的，堆可以在O（1）中findMin 或 findMax ，但不能在同一个数据结构中find。 然而，我不同意堆findMin / findMax更好。 事实上，只要稍作修改，BST可以在O（1）中同时做findMin 和 findMax 。

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

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

我会有兴趣听到你的想法在下面的评论。 谢谢 ：）

更新

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

Answer 5

二叉search树使用的定义是：对于每个节点，左边的节点具有较小的值（键），右边的节点具有较大的值（键）。

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

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

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

今天我在考试中跑了同样的问题，我说得没错。 微笑… 🙂

Answer 6

堆的另一个使用BST; 因为有一个重要的区别：

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

现在，让我们使用一个数据结构来存储航class的着陆时间。 如果着陆时间的差异小于“d”，我们不能安排航class降落。 并假设许多航class已经预定登陆一个数据结构（BST或堆）。

现在，我们要安排另一class飞机在t 。 因此，我们需要计算t与其后继者和前辈的差异（应该> d）。 因此，我们需要一个BST来实现这一点，如果平衡的话，它就是快速的， 即在O（logn）中。

编辑：

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

Answer 7

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

Answer 8

堆只是保证更高层次上的元素（最大堆）或更小（最小堆）比下层的元素

我喜欢上面的答案，并把我的评论更具体到我的需要和使用。 我必须得到n个位置列表，find每个位置到特定点的距离（0,0），然后返回距离较小的位置。 我使用的是堆的优先级队列。 为了find距离并将其放入堆中，每次插入都需要n（log（n））个n位置log（n）。 然后为了获得最短距离的m，需要m（log（n））m个位置的log（n）删除堆积起来。

如果用BST来做这件事，那么最坏的情况就是插入（假设第一个值非常小，而其他所有的依次是越来越长，并且树只跨越右边的小孩或者离开小孩如果是越来越小的话，min就会花O（1）次，但是我必须要平衡，所以从我的情况和以上的回答中我得到的结果是当你只是在min或者max的基础上为堆。