我什么时候想要使用堆?
除了优先级队列的明显答案外,在编程冒险中,堆何时会有用?
每当需要快速访问最大(或最小)的项目时使用它,因为该项目将始终是数组中的第一个元素或树的根目录。
但是,数组的其余部分保持部分未sorting。 因此,只能对最大(最小)的项目进行即时访问。 插入是快速的,所以这是处理传入事件或数据的好方法,并且始终可以访问最早的/最大的。
对于优先级队列,调度程序(最早的项目所在的地方)等有用。
堆是父节点的值大于其任何后代节点的树。
如果将堆看作深度按线性顺序存储的二叉树,则首先使用根节点(接下来是该节点的子节点,然后是这些节点的子节点); 那么指数N处的节点的孩子在2N + 1和2N + 2。 这个属性允许快速访问索引。 而且由于通过交换节点来操作堆,这就允许就地分类。
堆是旨在允许快速访问最小或最大的结构 。
但是你为什么要这样? 你可以检查添加每个条目,看它是最小的还是最大的。 这样你总是有最小的或最大的恒定时间O(1)
。
答案是因为堆允许你拉最小或最大,并迅速知道下一个最小或最大 。 这就是为什么它被称为优先级队列。
真实世界的例子(虽然不是很公平的世界)
假设你有一个医院,根据他们的年龄看病。 无论什么时候排队等候,最老的人总是先出席。
你不能只跟踪最古老的一个,因为如果你把他/她拉出来,你不知道下一个最老的。 为了解决这个医院问题,你实现一个最大的堆 。 根据定义,这个堆是部分有序的。 这意味着你不能根据年龄对病人进行分类,但是你知道最老的病人总是处在最前面,所以你可以在一个固定时间内把病人拖出来O(1)
并且在logging时间O(log N)
。
更复杂的例子:
假设你有一个整数序列,你想跟踪的median
,是中位数,具有相同数量的较小和较大的整数的整数。
例:
[1, 2, 5, 7, 23, 27, 31]
在上面的例子中, 7
是中位数,因为包含较小数字[1, 2, 5]
的数组的大小与包含较大数字[23, 27, 31]
[1, 2, 5]
的大小相同。 通常情况下,如果数组有偶数个元素,中位数是中间两个元素的算术平均数,例如(5 + 7)/2
。
现在,你如何跟踪中位数? 通过2堆 ,包含小于当前中值的数字的一分钟堆和包含大于当前中值的数的最大堆。 现在,如果这些堆总是平衡的,那么这两堆将包含相同数量的元素,或者一个元素比另一个元素多一个元素。
在序列中添加新元素时,如果数字小于当前的中位数,则将其添加到最小堆中,否则将其添加到最大堆中。 现在,如果堆不平衡(一个堆比另一堆多1个元素),则从最大的堆中抽取一个元素并将其添加到最小的堆中。 现在他们是平衡的。
堆的特点是它是一个维护数据半结构化的结构; 因此,维护一个完整的订单的成本和通过随机混乱进行挖掘的成本之间是一个很好的折衷。 该特性用于许多algorithm,如select,sorting或分类。
堆的另一个有用的特性是它可以从一个数组就地创build!
也适用于selectalgorithm(查找最小或最大)
任何时候当你sorting一个临时列表,你应该考虑堆。
如果要分别访问最小和最大的元素,可以使用minHeap或maxHeap。