前言

这一篇介绍的是一类特殊的数据结构——堆，以及堆的应用（优先队列、堆排序）。

堆

定义

堆是什么？字如其名，就是这样的（不是）：

开个玩笑，堆(Heap)是计算机科学中一类特殊的数据结构的统称，用于更方便寻找最大或最小的值。而堆的这种三角形结构，我们完全可以把它当成一颗完全二叉树来处理。

完全二叉树（complete binary tree）是除了最后一层可能没有填满外，所有的层都被填满的二叉树，且最后一层从左向右填充。即只有最后一层节点右边不放满的二叉树。

例如这样的树，它除了最后一层外其他层都满了，而且最后一层有填充的都从左往右。

当它最后一层全部填满以后，我们称为完美二叉树（完全平衡二叉树）：

一颗完全二叉树的高度为h，它拥有的节点数N为2h（最后一层有一个）~2h+1-1（最后一层满）

所以它的高度为logN，时间复杂度为O(logN)。

于是我们就有了一个结构——二叉堆（Binary Heap），满足：

  •  二叉堆是一颗完全二叉树。
  • 堆中某个节点的值总是不大于或不小于其父节点的值。

同时把某个节点的值总是不大于其父节点的值的堆称为最小堆，把某个节点的值总是不小于其父节点的值的堆称为最大堆。

即从上到下，上面的数永远比下面的数大的为最小堆，因为最小的在最上面；下面的数永远比上面的数大的为最大堆，因为最大的在最上面。

实现

实现堆我们可以同样像树一样使用链表结构实现，但在一些操作中会涉及很多的重复操作。例如插入结点，需要满足最小/最大堆的性质，我们需要先找到一个适合的位置，然后不断调整。这样的操作大多数可能时间复杂度都需要O(N)。而完全二叉树的时间复杂度为O(logN)，我们完全不使用任何指针操作，使用数组来实现。

首先我们给树中的节点从左到右、从上到下标一个号，然后按照标号遍历，这样的遍历是按层来遍历的。

我们把对应序号的节点值输入到对应序号的数组元素中去，于是有：

其中数组的首位置0是空的，我们把它当成一个指示结点（相当于链表中的哑结点，指向首节点）

对于数组中的结点i，它的值为array[i]，它的父母节点（若有）为i/2（整除），左节点为2i，右节点为2i+1。

因为我们不知道它最后一层有多少个元素，故我们使用动态数组会比较好。接下来的实现均以最小堆为例子。

于是乎，我们关于堆的定义：

typedef int ElementType;
struct HeapStruct
{
    int Capacity;    //最大容量
    int Size;    //当前大小
    ElementType *Elements;    //堆数组
};
typedef struct HeapStruct *Heap;

于是我们对它进行初始化为空堆。

Heap Initialize(int n)
{
    Heap H = (Heap)malloc(sizeof(struct HeapStruct));
    if(H==NULL)
    {
        printf("Out of space!\n");
        exit(-1);
    }
    H->Elements = (ElementType *)malloc((n+1)*sizeof(ElementType));
    if(H->Elements == NULL)
    {
        printf("Out of space!\n");
        exit(-1);
    }
    H->Capacity = n;
    H->Size = 0;
    H->Elements[ 0 ] = MinData;
    return H;
}

参数n为数组的大小，在申请数组的时候H->Elements开了n+1个，因为有一个标识节点0. MinData为一个极小的数，它一定比输入数组中的所有元素要小。此时我们找到的最小值一定在标识节点的下一位（根）处。

插入

对于堆的插入，我们可以先把它放在数组的最后，然后再进行调整。即如果我插入一个2.5：

因为一步到位需要搜索比较的范围比较广，还是先插入再调整比较好。接下来就是调整，我们会比较插入结点与其父母结点的大小，如果插入节点小则向上交换调整，否则就结束。这样的策略称为向上冒泡。

在此之前我们需要一些工具函数：

int IsEmpty(Heap H)
{
    return H->Size == 0;
}

int IsFull(Heap H)
{
    int n = sizeof(H->Elements)/sizeof(ElementType) - 1;    //n为输入数组的大小，即所有节点的个数
    return H->Size == n;
}

则插入函数为：

void Insert(ElementType X, Heap H)
{
    if(IsFull(H))
    {
        printf("Heap is full, cannot insert!\n");
        return;
    }
    realloc(H->Elements,sizeof(H->Elements) + sizeof(ElementType));    //在数组后面增添一个位置
    for(int i=++H->Size;i>=1;i/=2)
    {
        if(X < H->Elements[i/2])    //如果插入的值小于它的父母结点的值
        {
            H->Elements[i]=H->Elements[i/2];    //把父母结点的值赋到新开的数组
            continue;
        }
        else 
        {
            H->Elements[i] = X;
            break;
        }
    }
}

我们最初设置为标记结点Elements[0]为一个最小值，所以不存在超出根的情况。

删除最小元

我们删除最小元，即删除根节点，因为这是一个最小堆。

删除的过程是一个下沉操作，我们先记录删除元素的值以便返回。接下来通过比较得到根的左右结点和最后一个结点中的最小值，并把最小值赋值到根节点上。

  • 若左结点最小，则把左结点的值赋值到根结点上，然后以左节点为新的根继续寻找；
  • 若右结点最小，则把右结点的值赋值到根结点上，然后以右节点为新的根继续寻找；
  • 若最后一个结点最小，则把它赋值到根结点上，并停止寻找。

例如：

总结来说，删除最小元就是：

  1. 最后结点最小，它覆盖根结点，堆大小减一；
  2. 从根结点处进行堆下沉。

下沉，是指当前元素不断和左右两个孩子结点比较大小：与更小的结点值交换，直到到达叶子结点。我们使用循环来实现。

ElementType DeleteMin(Heap H)
{
    ElementType MinElement, LastElement;
    if(IsEmpty(H))
    {
        printf("Heap is empty!\n");
        return H->Elements[0];
    }
    MinElement = H->Elements[ 1 ];
    LastElement = H->Elements[H->Size--];
    for(int i=1;2*i<=H->Size;)
    {
        if(H->Elements[i*2] < H->Elements[i*2+1] && H->Elements[i*2] < LastElement) //左结点比右结点和最后结点小 
        { 
            H->Elements[i] = H->Elements[i*2];
            i*=2;
        }
        else if(H->Elements[i*2+1] < H->Elements[i*2] && H->Elements[i*2+1] < LastElement) //右结点比左结点和最后结点小  
        { 
            H->Elements[i] = H->Elements[i*2+1];
            i=i*2+1;
        }
        else if(LastElement < H->Elements[i*2] && LastElement < H->Elements[i*2+1])    //最后一个结点最小
        {
            H->Elements[i] = LastElement;
            break;
        }
    }
    return MinElement;
}

实现总结

我们使用堆一般是需要快速寻找其最大最小值的，对于这些操作具有比较友好的时间复杂度：

  • 插入操作，操作数为h（高度），时间复杂度是
  • 删除操作，操作数为h（高度），时间复杂度是 
  • 获取堆顶，时间复杂度是 

我们数据根据堆来存储，获取堆顶就是获取根节点的值即可。

ElementType FindMin(Heap H)
{
    if(IsEmpty(H))
    {
        printf("Heap is empty!\n");
        return H->Elements[0];
    }
    return H->Elements[1];
}

这是最小堆的实现过程，而对于最大堆，我们的操作也类似。即插入时上浮比较大小并替换，删除时下沉比较大小并替换。

关于堆，有两个非常经典的应用——优先队列和堆排序。

优先队列

假设我们去超市购买东西，超市结账规则有一条，若用户是VIP则优先结账，VIP等级越高越优先。我们排队结账原本是一个普通的队列，加上这一条规则后，就是在队列的基础上让优先级高的人（VIP等级高）先结账，这样的队列就是个优先队列。

优先队列是按照优先级顺序出队的队列，优先级高的在前出队。

如果我们用标号来表示优先级，标号越小优先级越高。那么我们发现，此时的优先队列和堆的结构很像，我们可以使用堆来处理优先队列。

故我们只需要让需要优先出队的元素插入在标号小的位置即可，此时我们可以直接使用上面的堆ADT来操作。

堆排序

堆排序是堆最常见的一个应用。因为堆的性质导致我们找到最大最小值非常简单，取出最大或最小值时间复杂度为

我们可以新建一个数组，把每次取出的最小/最大值放到数组的指定位置，有N个数，时间复杂度为O(N)。

当然如果我们就在当前数组下进行操作，就能降低其空间复杂度，防止浪费。我们此时一般使用最大堆进行操作，因为每次删除最大元出来的是局部最大值，我们就可以把它放在数组的尾部，这样删除全部的表以后它就是个从小到大有序的数列了。

当然我们删除最小堆也是可以的，此时放在数组后面的为最小值，最后得到的是从大到小有序的数列。

注意我们最好不要删除最小堆的最小元放到最前面，会破坏堆的标识结构。

我们用最大堆举个例子：

我们删除一个元素需要

我们采用之前的堆ADT，并使用最小堆作为例子，其代码：

Heap Heapsort(ElementType A[], int n)    //基于最小堆的排序，最后得到的H为从大到小序列
{
    Heap H=Initialize(n);    //新建堆
    for(int i=0;i<n;i++)    //插入堆
    {
        Insert(A[i],H);
    }
    for(int i=1;i<=n;i++)    //删除n个数
    { 
        H->Elements[H->Size+1]=DeleteMin(H);    //把删除的数放在数组的最后
    }
    return H;
}

这里的H->size因为删除时已经被减一了，此时最后一位是不在堆里的，故此时需要H->size+1.最后如果我们需要从小到大排序，只需要从后往前输出即可。

在稳定性上，和快速排序一样， 堆排序的过程中有交换元素的操作，所以堆排序也是不稳定的排序算法 ；稳定性是指，值相同的元素在操作前后的相对顺序应该不变。

相比快速排序，堆排序有一个缺点，就是局部性差, 我们可以发现，无论是上浮还是下沉的方式，在交换元素的时候， 会导致元素大距离的移动，对实际中的缓存利用不友好。

后记

这一篇介绍的是一类特殊的数据结构——堆，以及堆的应用（优先队列、堆排序）。

参考资料：https://writings.sh/post/data-structure-heap-and-common-problems

这里的一切都有始有终，却能容纳所有的不期而遇和久别重逢。
最后更新于 2024-01-14