二叉堆数据结构 - 应用

Question

根据我的理解，二叉堆（数据结构）用于表示优先队列ADT。它是一个满足“堆属性”的完全二叉树。

“堆属性”——如果A是B的父节点，则节点A的键（值）按照和整个堆相同的顺序与节点B的键排序。

首先，它帮助我记住术语“堆”，因为对这种数据结构称为“堆内存”。词汇“堆”的字典含义是一堆杂乱无章的东西。

问题：

在学习Reb-Black树和AVL树数据结构之后，

为什么我们要考虑新的数据结构（二叉堆）？

二叉堆是否解决了红黑树或AVL树无法适应的问题？

- overexchange

---

二叉堆的首次已知引用出现在J.W.J.威廉姆斯的堆排序实现中（Williams，J.W.J.（1964），“Algorithm 232：Heapsort”，ACM通讯7（6），347-348）。归咎于他的名字。 - Jim Mischel

Answer 1

二叉堆和红黑树的主要区别在于某些操作的性能。

二叉堆

优点

• 是理想的优先级队列，因为最小/最大元素（取决于您的实现）始终具有O(1)的访问时间，因此不需要搜索。
• 对于插入新值也非常快（平均情况下为O(1)，最坏情况下为O(log(n))。

缺点

• 随机元素的查找速度较慢。

---

红黑树

优点

• 具有更好的搜索和插入性能。

缺点

• 最小/最大搜索速度较慢。
• 总体上有更多的开销。

应注意的是，红黑树也可以成为良好的调度程序，例如Linux内核v2.6中引入的完全公平调度程序。

- Cloud

---

我想进一步阐述，堆和二叉搜索树（RB、AVL等）试图实现不同的目标。堆的目的是能够在排序函数的一端找到一组对象中的对象。堆不适用于搜索单个元素。另一方面，二叉搜索树非常适合搜索，但不适合查找最小/最大元素。这两种数据结构都提供了高效的插入和删除元素的方法。 - Andy Schweig

为什么使用“堆”这个术语？根据其含义，有没有给出这个术语的任何原因？ - overexchange

关于名称的词源学，二叉堆是“满足‘堆’数学属性的二叉树”。它与常用语言中的“堆”不是在相同的上下文中使用。 - Cloud

堆的另一个优点是，构建初始N个元素的堆的摊销复杂度为O(N)，即线性时间。但对于二叉搜索树而言，其复杂度为NlogN。 - Sazzad Hissain Khan