堆 算法实现
程序员文章站
2024-02-15 09:57:28
...
堆可以解决下面两个重要问题
- 排序:采用堆排序算法对n元素数组排序,所花的时间不会超过O(nLogn),而且只需要几个字的额外空间。
- 优先级队列:堆通过插入新元素和提取最小元素这两种操作来维护元素集合,每个操作所需的时间都为O(log n);
堆的性质(最小堆)
- 任何节点的值都小于或等于其子节点的值。这意味着集合的最小元素位于根节点。
- 最底层的叶节点尽可能地靠左分布。树中不存在空闲的位置。
- 所有节点到根节点的距离不超过logn
堆与数组的关系
创建一下堆:
对应的数组关系:
从两者的对应关系可以看出:12元素使用x[12+1]的数组表示。第0位为空。
root = 1
value(i) = X[i];
leftChild(i) = 2*i
rightChild(i) = 2*i +1
parent(i) = i/2
注:整数的除法是向下取整(如3/2 = 1)
往堆中插入元素
在堆中插入一个元素,它始终保持一下的性质:
除了新插入的元素i和它的父节点不具备堆的性质外,其余部分总是保持堆的性质。
如果i==1位真,那么节点i没有父节点,那么所有地方都具有堆性质,因此可以终止循环。
当节点i有父节点时,可以通过赋值语句p=i/2使p成为父节点的下标。如果x[p] <= x[i],那么所有地方都具有堆性质,循环可以终止。
伪代码实现如下:
void siftup(n)
pre n > 0 && heap(1,n-1)
post heap(1,n)
i=n
loop
//invariant:heap(1,n) except perhaps between i and its parents
if i == 1
break
p = i/2
if (x[p] <= x[i])
break;
swap(p,i)
i = p
从堆顶删除元素
当从堆顶删除一个元素i时,删除原理如下:
- 首先检查节点i是否具有子节点,如果没有,就终止循环。
- 如果节点i具有子节点,那么把变量c设置为较小的那个子节点的下标。最后,或者满足X[i] <= X[c]终止循环。
- 或者通过交换x[i] 和x[c]并赋值i=c继续进行到循环底部。
void siftdown(i)
pre heap(2,n) && n >= 0
post heap(1,n)
i=1
loop
//invariant:heap(1,n) except perhaps between i and its (0,1 or 2) children
c = 2*i
if c > n
break
if c +1 <= n
if X[c+1] < x[c]
c++
if x[i] <= x[c]
break
swap(c,i)
i = c
堆的应用一:优先级队列
优先级队列实现的数据结构介绍
优先级队列主要包含两种操作:一个入队,另一个是出队。根据应用场景选取不同数据结构的实现
数据结构及运行时间 | 一次Insert | 一次extractmin | 两次操作各n次 |
---|---|---|---|
有序序列(数组) | O(n) | O(1) | O(n2) |
堆 | O(logn) | O(logn) | O(nlogn) |
无序序列(列表) | O(1) | O(n) | O(n2) |
堆的应用二:排序
首先在优先级队列中依次插入每个元素,然后按序删除它们。由于该算法使用了n-1次siftup和n-1次siftdown,而每次操作的开销最多为O(logn),因此即使在最坏情况下,该算法的运行时间也是O(nlogn)。
堆的应用三:从10亿个数的文件中找出最大的100万个数。
上一篇: PriorityQueue详解