二叉堆(binary heap)

时间：2023-03-08 17:37:51

　堆(heap) 亦被称为：优先队列(priority queue)，是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

本文地址：http://www.cnblogs.com/archimedes/p/binary-heap.html，转载请注明源地址。

逻辑定义

n个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆：
(ki <= k2i, ki <= k2i+1)或者(ki >= k2i, ki >= k2i+1),   (i = 1,2,3,4...n/2)

二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1。因此，第1个位置的子节点在2和3，第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。

如果存储数组的下标基于0，那么下标为i的节点的子节点是2i + 1与2i + 2；其父节点的下标是⌊(i − 1) ∕ 2⌋。

如下图的两个堆：

        1               11

      /   \           /   \

     2     3         9     10

    / \   / \       / \    / \

   4   5  6  7     5   6  7   8

  / \ / \         / \ / \

 8  9 10 11      1  2 3  4

将这两个堆保存在以1开始的数组中：

位置:  1  2  3  4  5  6  7  8  9 10 11

左图:  1  2  3  4  5  6  7  8  9 10 11

右图: 11  9 10  5  6  7  8  1  2  3  4

性质

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

二叉堆(binary heap)            二叉堆(binary heap)

最小堆                                                           最大堆

堆支持以下的基本操作:

  • build：建立一个空堆；
  • insert：向堆中插入一个新元素；
  • update：将新元素提升使其符合堆的性质；
  • get：获取当前堆顶元素的值；
  • delete：删除堆顶元素；
  • heapify：使删除堆顶元素的堆再次成为堆。

某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。

基本操作实现：

1、删除优先级最高的元素（DeleteMin）

此操作分3步：

（1）直接删除根

（2）用最后一个元素代替根

（3）将堆向下重新调整

　　输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直到是叶子结点或其关键字值小于等于左、右子树的关键字的值，将得到新的堆。称这个从堆顶至叶子的调整过程为“筛选”

二叉堆(binary heap)

调整堆算法实现如下：

void down(int p)  /* 调整堆算法 */

{

    int q = p * ;   /* 向下调整算法，p代表当前结点，q代表子结点 */

    a = heap[p];    /* 保存当前结点的值 */

    while(q <= hlength) {    /* hlength为堆中元素的个数 */

        /* 选择两个子节点中的一个最小的 */

        if(q < hlength && heap[q] > heap[q + ])

            q++;

        if(heap[q] >= a) {    /* 如果当前结点比子节点小，就结束*/

            break;

        } else {             /* 否则就交换 */

            heap[p] = heap[q];

            p = q;

            q = p * ;

        }

    }

    heap[p] = a;    /* 安排原来的结点 */

}

删除最小元素，返回该最小元素：

int DeleteMin()

{

    /* 删除最小元素算法 */

    int r = heap[];   /* 取出最小元素 */

    heap[] = heap[hlength--];  /* 把最后一个叶子结点赋值给根结点 */

    down();    /* 调用向下调整算法 */

    return r;

}

2、在堆中插入一个新元素Insert(x):

向上调整算法：

void up(int p)

{

    /* 向上调整算法，p代表当前结点，q代表父结点 */

    int q = p / ;  /* 获取当前结点的父结点 */

    a = heap[p];    /* 保存当前结点的值 */

    while(q >=  && a < heap[q]) {

        heap[p] = heap[q];  /* 如果当前结点的值比父母结点的值小，就交换 */

        p = q;

        q = p / ;

    }

    heap[p] = a;   /* 安排原来的结点 */

}

插入元素算法：

void insert(int a)

{

    heap[++hlength] = a;  /* 先往堆里插入结点值 */

    up(hlength);  /* 向上调整 */

}

3、将x的优先级上升为p：

void IncreaseKey(int a, int p)  /* 把p的优先级升为a */

{

    if(heap[p] < a)

        return;

    heap[p] = a;

    up(p);

}

4、建立堆:

void bulid()  /* 建堆算法 */

{

    int i;

    for(i = hlength / ; i > ; i--)

        down(i);   /* 从最后一个非终端结点开始进行调整 */

}

编程实践

poj2051 Argus

http://poj.org/problem?id=2051

#include<stdio.h>

#include<string.h>

char str[];

typedef struct Node {

    int now, Q, P;

}Node;

Node node[];

void down(Node H[], int s, int m)

{

    int j;

    Node rc = H[s];

    for(j = s * ; j <= m; j *= ) {

        if(j < m) {

            if(H[j].now > H[j + ].now) {

                j++;

            } else {

                if((H[j].now == H[j + ].now) && (H[j].Q > H[j + ].Q))

                    j++;

            }

        }

        if(rc.now < H[j].now || (rc.now == H[j].now && rc.Q < H[j].Q))

            break;

        H[s] = H[j];

        s = j;

    }

    H[s] = rc;

}

void BulidMinHeap(Node H[], int length)

{

    int i;

    for(i = length / ; i > ; i--)

        down(H, i, length);

}

void solve()

{

    int i, len, K;

    i = ;

    while(scanf("%s", str) && str[] == 'R') {

        scanf("%d %d", &node[i].Q, &node[i].P);

        getchar();

        node[i].now = node[i].P;

        i++;

    }

    len = i - ;

    scanf("%d", &K);

    BulidMinHeap(node, len);

    for(i = ; i <= K; i++) {

        printf("%d\n", node[].Q);

        node[].now += node[].P;

        down(node, , len);

    }

}

int main()

{

    solve();

    return ;

}

参考资料

1、Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein（潘金贵等译）《算法导论》. 机械工业出版社.

2、Vuillemin, J. (1978). A data structure for manipulating priority queues.Communications of the ACM21, 309–314.

3、ACM/ICPC 算法训练教程

4、《数据结构》严蔚敏、吴伟民

5、*

相关文章