数据结构什锦（五点五）——优先队列和堆

在学习图论时遇到一点阻碍，涉及到路径规划算法部分涉及到了优先队列的知识点。所以，作为前置知识，我们先来学习一下优先队列。

什么是优先队列

优先队列与队列的听起来很像，区别在于：优先队列是根据元素的优先级而不是先进先出的顺序来处理数据。比如一个作业调度系统，决定作业调度顺序的是作业优先级而不是先进先出原则。故我们要从一堆元素中找出元素的最大值/最小值，就可以使用优先队列ADT进行操作。优先队列是一种支持插入、删除最小值（删除并返回最小值）、删除最大值（删除并返回最大值）操作的数据结构。

如果具有最小关键字的元素具有最高优先级（总是删除最小元素），那么这种优先队列被称为上升优先（ascending-priority）队列。类似的，如果具有最大关键字的元素具有最高优先级（总是删除最大元素），那么这种队列就是下降优先级（descending-priority）队列。因为这两种队列是对称的，所以我们仅讨论上升优先队列。

抽象数据类型

我们先给出该ADT的操作部分。

主要操作

优先队列是一种数据元素的容器，每个元素具有一个关联的关键字。

Insert（key,data）:插入一个关键字为key的数据元素到优先队列中，数据元素基于关键字有序。
DeleteMin/DeleteMax：删除并返回具有最小值/最大值关键字的元素。
GetMinimum/GetMaximum：返回具有最小/最大关键字的元素。

辅助操作

第k小/第k大：返回优先队列中第k小/第k大的元素
大小：返回优先队列中的数据元素个数
堆排序：基于优先级（关键字）对优先队列中的数据进行排序

应用

优先队列有很多应用。

数据压缩：Huffmanm编码算法
最短路径算法：Dijkstra算法
最小生成树算法：Prim算法
事件驱动仿真：客户排队
选择问题：查找第k小的元素

实现

下面我们来探讨优先队列的具体实现，接下来我们来给出优先队列的几种可能的实现方式。

基于无序数组的实现

元素插入数组时不考虑排序，每次删除操作时先搜索最小关键字再进行操作。

基于无序链表的实现

这种实现方式和基于无序数组的实现方式非常相似，只不过使用的是链表而非数组罢了。

基于有序数组的实现

基于数组元素的关键字进行排序，我们将数据插入到数组适当的位置上，这样在删除元素时只需要在数组的一端进行操作。

基于有序链表的实现

基于数据元素关键字的排序顺序，将数据元素插入在链表的适当位置上，删除元素只需要在链表的一端进行，这样既保留了优先队列的状态，又可以继续使用其他的链表ADT相关函数。

基于二叉树的实现

如果插入的元素是随机给定的，那么插入和删除操作的平均时间复杂度将降至O(log_n)。

基于平衡搜索二叉树的实现

插入和删除操作的最坏时间复杂度为O(log_n)。

基于二项堆的实现

接下来我们将详细讨论这种实现方式。它的搜索、插入和删除操作时间复杂度均为O(log_n)，查找最大或最小元素的操作为O(1)。

堆和二项堆

堆是具有某种特定性质的树。堆的基本要求是：其节点的值必须大于等于（或者小于等于）它孩子节点的值。这被称为堆的性质。堆还拥有其他性质：比如某h>0的堆，其叶子节点全部分布在第h层或者h－1层(参考完全二叉树)。这意味着，堆应该看起来像是一棵完全二叉树。

  
graph TB;
1((1))-->2((2))
1((1))-->3((3))
2((2))-->4((4))
2((2))-->5((5))

根据堆的性质，我们可以把堆分为两类。

小顶堆（min heap）：节点的值必须小于等于它孩子节点的值。（两个都得小与，故我这本书p207这里的图是错误的）
大顶堆（max heap）：节点的值必须大于等于它孩子节点的值。

二项堆

在二项堆中，每个节点最多只能有两个孩子。在实际应用中，二项堆已经够用了，所以接下来我们将着重讨论二项小顶堆（binary min heap）和二项大顶堆（binary max heap）。

根据我们前面介绍的实现方法，我们既可以用数组来线性存储，也可以用指针来链式存储。这里我们主要学习一下利用数组来实现的堆。

注意：以下的讨论我们都是假设在大顶堆上进行操作的。

声明

堆的声明代码如下。

struct Heap{
    int *array;
    int count;//堆中数据元素的个数，即堆的大小
    int capacity;//堆的容量
    int heap_type;//小顶堆或大顶堆
};

创建堆

创建堆的代码实现如下。

struct Heap*CreatHeap(int capacity,int heap_type){
    struct Heap*h=(struct Heap*) malloc(sizeof (struct Heap));
    if(h==NULL){
        printf("Memory Error.");
        exit(-1);
    }
    h->heap_type=heap_type;
    h->count=0;
    h->capacity=capacity;
    h->array=(int *) malloc(sizeof (int)*capacity);
    if(h->array==NULL){
        printf("Memory Error.");
        exit(-1);
    }
    
    return h;
}

节点的双亲

位于第i个位置的元素它的双亲节点位于第i-1/2的位置上。比如第二个位置的元素的双亲结点在第0个位置上。

代码实现如下。

int parent(struct Heap*h,int i){
    if(i<=0||i>=h->count)
        return -1;
    return (i-1)/2;
}

节点的孩子

类似于上面对双亲的讨论，第i个位置的节点的孩子分别在2*i+1和2*i+2的位置上。

代码实现如下。

int LeftChild(struct Heap*h,int i){
    int left=2*i+1;
    if (left>=h->count)
        return -1;
    return left;
}

int RightChild(struct Heap*h,int i){
    int right=2*i+2;
    if (right>=h->count)
        return -1;
    return right;
}

获取最大值元素

因为在大顶堆中最大值元素总是位于根，所以它被存入h->array[0]。

int GetMaximum(struct Heap*h){
    if(h->count==0)
        return -1;
    return h->array[0];
}

调整堆元素

插入元素到堆后，可能无法满足堆的性质。这时我们就要调整堆中元素的位置使其重新成为堆，这个过程称为堆调整。

在大顶堆中，如果我们要进行堆调整，那么我们就找到不符合堆性质的节点，交换其与其孩子节点的最大值，然后重复这个步骤直到每个节点都满足堆的性质为止。

比如现在我们有一颗树，它的元素1并不满足堆的性质。

  
graph TB;
1((31))-->2((1))
1((31))-->3((21))
2((1))-->4((5))
2((1))-->5((10))
3((21))-->6((12))
3((21))-->7((18))
4((5))-->8((3))
4((5))-->9((2))
5((10))-->10((8))
5((10))-->11((7))

为了调整元素1，我们找到它的最大孩子10.然后对其交换位置。

  
graph TB;
1((31))-->5((10))
1((31))-->3((21))
5((10))-->4((5))
5((10))-->2((1))
3((21))-->6((12))
3((21))-->7((18))
4((5))-->8((3))
4((5))-->9((2))
2((1))-->10((8))
2((1))-->11((7))

还是不符合堆的性质，现在继续互选元素1和元素8。

  
graph TB;
1((31))-->5((10))
1((31))-->3((21))
5((10))-->4((5))
5((10))-->10((8))
3((21))-->6((12))
3((21))-->7((18))
4((5))-->8((3))
4((5))-->9((2))
10((8))-->2((1))
10((8))-->11((7))

现在这棵树满足堆的性质了。由于我们是自顶向下的方向来进行堆调整，所以我们称这种方法为向下渗透（percolate down）。

代码实现如下。

void PercolateDown(struct Heap*h,int i){
    int l,r,max,temp;
    l= LeftChild(h,i);
    r= RightChild(h,i);
    if(l!=-1&&h->array[l]>h->array[i])
        max=l;
    else
        max=i;
    if(r!=-1&&h->array[r]>h->array[max])
        max=r;
    if(max!=i){
        //互换h->array[i]和array[max]
        temp=h->array[i];
        h->array[i]=h->array[max];
        h->array[max]=temp;
        //重复递归直到顺序正常，最坏的情况就是到达某个叶子节点
        PercolateDown(h, max);
    }
}

删除元素

堆只支持删除根节点元素的操作，也就是删除最大元素。在删除最大元素后，我们将最后一个节点移动到根节点，然后对根节点重新调用向下渗透来调整堆元素。简而言之分为三步：

复制根节点元素到某个变量并准备返回
复制最后一个节点的元素到第一个元素的位置/根节点
对第一个节点/根节点调用向下渗透

代码实现如下。

int DeleteMax(struct Heap*h){
    int data;
    if(h->count==0)
        return -1;
    data=h->array[0];
    h->array[0]=h->array[h->count-1];
    h->count--;//堆大小减一
    PercolateDown(h,0);
    return data;
}

插入元素

插入元素与删除元素的步骤类似，都可以简单的分为三步。

堆大小加一
将元素存放在堆/树的末端
自底向上对该元素进行堆调整

同样的，我们可以用图例来说明自底向上法是怎么进行的。假设我们向堆的末端插入了一个元素24。

  
graph TB;
1((31))-->5((10))
1((31))-->3((21))
5((10))-->4((5))
5((10))-->10((8))
3((21))-->6((12))
3((21))-->7((18))
4((5))-->8((3))
4((5))-->9((2))
10((8))-->2((1))
10((8))-->11((7))
6((12))-->12((24))

调整堆，将24与其双亲结点进行比较，调换24与其双亲结点12。

  
graph TB;
1((31))-->5((10))
1((31))-->3((21))
5((10))-->4((5))
5((10))-->10((8))
3((21))-->12((24))
3((21))-->7((18))
4((5))-->8((3))
4((5))-->9((2))
10((8))-->2((1))
10((8))-->11((7))
12((24))-->6((12))

重复以上步骤，继续调换24与21。

  
graph TB;
1((31))-->5((10))
1((31))-->12((24))
5((10))-->4((5))
5((10))-->10((8))
12((24))-->3((21))
12((24))-->7((18))
4((5))-->8((3))
4((5))-->9((2))
10((8))-->2((1))
10((8))-->11((7))
3((21))-->6((12))

此时该堆满足堆的性质，调整完毕。因为我们是自底向上进行调整，所以我们称这种方法为向上渗透（percolate up）。

那么，插入的代码实现如下。

void ResizeHeap(struct Heap*h){//把堆大小扩大至原先的两倍
    int *array_old=h->array;
    h->array=(int*) malloc(sizeof (int)*h->capacity*2);
    if(h->array==NULL){
        printf("Memory Error.\n");
        exit(-1);
    }
    for (int i = 0; i < h->capacity; ++i) {
        h->array[i]=array_old[i];
    }
    h->capacity*=2;
    free(array_old);
}

void Insert(struct Heap*h,int data){
    int i;
    if(h->count==h->capacity)
        ResizeHeap(h);
    h->count++;
    i=h->count-1;
    while (i>=0&&data>h->array[parent(h,i)]){
        //如果i大于零且要插入的数据比最后一个节点的双亲节点值要大
        //就把双亲结点移动到最后一个节点的位置
        //注意，此时最后一个节点没有插入数据，也就是说移动后的双亲结点位置的值是未定义的
        h->array[i]=h->array[parent(h,i)];
        i= parent(h,i);
    }
    h->array[i]=data;//最后才讲data的值插入到正确的位置
    //然而我觉得开始时就先插入data的值，最后只要交换成功就完成会不会更好
}

撤销堆

堆的主要几个操作都介绍完毕了，最后我们要做的就是在程序关闭前释放堆的内存空间。

代码实现如下。

void DestroyHeap(struct Heap*h){
    if(h==NULL)
        return;
    free(h->array);
    free(h);
    h=NULL;
}

将数组调整成堆

建立堆的一个简单的方法是把n个输入元素放入一个空堆中。我们这里把元素直接存入一个数组，再把数组中的元素调整成堆。

首先我们考虑叶子节点。因为叶子节点无论如何都满足堆的性质，所以我们只需要关注非叶子节点的顺序。如何找到非叶子节点呢？我们知道最后一个叶子节点必然在h->count-1位置上，所以我们可以直接找到最后一个叶子节点的双亲来找到第一个非叶子节点，再对每一个非叶子节点应用向下渗透调整堆就可以了。

具体的代码实现如下。

void BuildHeap(struct Heap*h,int A[],int n){
    if(h==NULL)
        return;

    while (n>h->capacity)
        ResizeHeap(h);

    for (int i = 0; i < n; ++i) {
        h->array[i]=A[i];
    }
    
    h->count=n;
    for (int i = (n-1)/2; i >=0 ; i--) {
        PercolateDown(h,i);
    }
}

堆排序

堆排序算法是排序算法中一个较为优秀的算法，它的时间复杂度只有O(n·log_n)。

堆排序算法从一个无序数组中插入所有的元素进入堆中，然后再从元素的根节点处不断的删除元素直到堆为空为止。实际上就是把一个数组调整为堆，然后不断的按照出队最大元素/最小元素来进行排序。

堆排序也可以通过数组实现。此时不是删除元素，而是通过交换第一个元素和最后一个元素，并减小堆大小来实现。然后我们对第一个元素再进行堆调整，持续这个过程直到堆中只剩下一个元素为止。

代码实现如下。

void Heapsort(int A[],int n,int heap_type){
    struct Heap*h= CreatHeap(n,heap_type);
    int old_size,i,temp;
    BuildHeap(h,A,n);
    old_size=h->count;

    for (i = n-1;  i>0 ; i--) {
        //h->array[0]是最大的元素
        temp=h->array[0];
        h->array[0]=h->array[h->count-1];
        h->array[h->count-1]=temp;
        h->count--;
        PercolateDown(h,0);
    }
    h->count=old_size;
}