欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆 算法实现

程序员文章站 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万个数。