我什么时候想要使用堆？

Question

除了优先级队列的明显答案之外,什么时候堆在我的编程冒险中会有用？

Answer 1

只要您需要快速访问最大(或最小)项,就可以使用它,因为该项始终是数组中的第一个元素或树的根.

但是,数组的其余部分保持部分未排序.因此,只能对最大(最小)的项目进行即时访问.插入速度很快,因此它是处理传入事件或数据的好方法,并且始终可以访问最早/最大的事件.

对优先级队列,调度程序(需要最早的项目)等有用...

堆是一个树,其中父节点的值大于其任何后代节点的值.

如果您认为堆是按深度线性顺序存储的二叉树,首先是根节点(然后是该节点的子节点,然后是那些节点的子节点); 然后索引N处的节点的子节点为2N + 1和2N + 2.此属性允许快速访问索引.并且由于堆叠是通过交换节点来操纵的,因此可以进行就地排序.

Answer 2

堆是允许快速访问最小或最大的结构.

但你为什么要这样呢？您可以检查添加的每个条目,看它是最小的还是最大的.这样,您在恒定时间内始终拥有最小或最大O(1).

答案是因为堆可以让你拉最小或最大,并迅速知道NEXT最小或最大.这就是为什么它被称为优先级队列.

现实世界的例子(不是非常公平的世界):

假设您有一家医院,患者根据其年龄参加.无论他/她何时排队,最老的人总是先出席.

你不能只跟踪最老的那个,因为如果你拉出他/她,你就不知道下一个最老的那个.为了解决这个医院问题,你实现了最大堆.根据定义,此堆是部分排序的.这意味着您无法按年龄对患者进行分类,但您知道最老的患者总是处于最顶层,因此您可以在一段时间内将患者拉出来并在对数时间内O(1)重新平衡堆O(log N).

更复杂的例子:

假设你有一个整数序列,你想跟踪它median.中位数是有序数组中间的数字.

例:

[1, 2, 5, 7, 23, 27, 31]

在上面的例子中,7是中位数,因为包含较小数字的数组与包含较大数字的数组[1, 2, 5]的大小相同[23, 27, 31].通常,如果数组具有偶数个元素,则中位数是中间的2个元素的算术平均值,例如(5 + 7)/2.

现在,你如何跟踪中位数？通过有2个堆,一个包含小于当前中位数的数字的最小堆和包含大于当前中位数的数字的最大堆.现在,如果这些堆总是平衡的,那么2个堆将包含相同数量的元素,或者一个元素将比另一个更多,最多.

向序列添加新元素时,如果该数字小于当前中位数,则将其添加到最小堆中,否则,将其添加到最大堆中.现在,如果堆是不平衡的(一个堆比另一个堆多1个元素),则从最大的堆中拉出一个元素并添加到最小的堆中.现在他们是平衡的.

Answer 3

堆的特征是它是一个保持数据半静态的结构; 因此,在维持完整订单的成本与通过随机混乱进行搜索的成本之间进行良好的权衡.该特征用于许多算法,例如选择,排序或分类.

堆的另一个有用特性是它可以从数组就地创建!