二进制堆数据结构.应用

Question

根据我的理解，

二进制堆(数据结构)用于表示优先级队列ADT。它是一个完全满足堆属性的二叉树。

堆属性-如果A是B的父节点，则节点A的键(值)相对于节点B的键进行排序，并在堆中应用相同的顺序。

首先，它帮助我记住术语堆，如果将这个数据结构命名为堆是有原因的。因为，我们还使用了堆内存这个术语。

“堆”的字典意思--乱七八糟地堆起来的东西。

问题，

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

为什么我们要考虑新的数据结构(二进制堆)？

二进制堆是否解决了红黑或AVL树不适合的一组问题？

Answer 1

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

二进制堆

优点

• 它是一个理想的优先级队列，因为min/max元素(取决于您的实现)总是O(1)访问时间，因此不需要搜索它。
• 它也非常快速地插入新的值(平均O(1)，O(log(n))最坏的情况)。

缺点

• 缓慢搜索随机元素。

RB树

优点

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

缺点

• 较慢的最小/最大搜索速度。
• 一般更多的开销。

应该注意的是，RB树也可以做出很好的调度器，例如LinuxKernelv2.6中引入的完全公平调度。