前言

堆是一个比较基础，且实现起来难度也不算太大的一个数据结构。而且堆在很多地方都有较好的应用。

堆

堆的引入

考虑一颗完全二叉树，如果你要从里面找到值最大的数据，怎么找？是不是得遍历整棵树，才能找到一个值。这样做的复杂度为$O(n)$。如果要在这棵树中频繁查找最值的话，这样的效率显然不能满足我们的需求。由此想到，也许我们可以对这颗树进行一些处理，让数据按照某种规则排列，从而方便查找最值。而堆就是这样一种数据结构。

堆的定义

堆作为一种数据结构，底下有很多具体的分支，比如二项堆和斐波那契堆。现在我们介绍一种最最基础的堆——二叉堆。在许多地方，二叉堆又简称为堆。在本文中，如无特殊声明，堆默认指二叉堆。
二叉堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆）；或者每个结点的值都大于或等于其左右孩子的值（称为大根堆）。以小根堆为例（下面的代码也是以小根堆为例），如果将堆按层序从1开始编号，则结点之间满足如下关系：
{ki≤k2iki≤k2i+1(1≤i≤⌊n/2⌋)\\begin{cases} k_i\\leq k_{2i} \\\\ k_i\\leq k_{2i+1} \\tag{$1\\leq i\\leq \\lfloor n/2 \\rfloor$} \\end{cases}{ki​≤k2i​ki​≤k2i+1​​(1≤i≤⌊n/2⌋)

堆的储存结构

由于堆是完全二叉树，因此采用顺序存储。值得一提的是，堆实际上是一种树结构，但堆的经典实现方法是使用数组。堆按层序从1开始连续编号，将结点以编号为下标存储到一维数组中。若一个结点的编号为$i$，则它的左儿子结点编号为$2i$，右儿子结点编号为$2i+1$，父亲结点编号为$\lfloor i/2\rfloor$。

typedef struct
{DataType data[Maxsize];int rear;
} PriQueue;

优先队列

优先队列简介

优先队列是按照某种优先级进行排列的队列，优先级越高的元素出队越早，优先级相同者按照先进先出的原则进行处理。优先队列的基本算法可以在普通队列的基础上修改而成。例如，入队时将元素插入到队尾，出队时找出优先级最高的元素出队；或者入队时将元素按照优先级插入到合适的位置，出队时将队头元素出队。这两种实现方法，入队或出队总有一个时间复杂度为$O(n)$。采用堆来实现优先队列，入队（即插入结点）和出队（即删除根结点）的时间复杂度均为O(log2n)O(log_2 n)O(log2​n)。

优先队列的基础操作

入队

优先队列的入队操作，即堆的插入结点操作。
在数组的最末尾插入新结点。然后自下而上调整子节点与父结点：比较当前结点与父结点，不满足堆性质则交换。从而使得当前子树满足二叉堆的性质。时间复杂度为O(log2n)O(log_2 n)O(log2​n) 。

void EnQueue(PriQueue *Q,DataType x)
{int i,temp;if (Q->rear==Maxsize-1) {printf("上溢");exit(-1);}Q->rear++;i=Q->rear;Q->data[i]=x;while(i/2>0&&Q->data[i/2]>x){temp=Q->data[i];Q->data[i]=Q->data[i/2];Q->data[i/2]=temp;i=i/2;}
}

出队

优先队列的出队操作，即堆的删除根结点操作。删除根结点之后，需要维护堆的性质。
对于最大堆，删除根结点就是删除最大值；对于最小堆，是删除最小值。然后，把堆存储的最后那个结点移到填在根结点处。再从上而下调整父结点与它的子结点：对于最大堆，父结点如果小于具有最大值的子节点，则交换二者。直至当前结点与它的子节点满足堆性质为止。时间复杂度也是O(log2n)O(log_2 n)O(log2​n) 。

DataType DeQueue(PriQueue *Q)
{int i,j,x,temp;if (Q->rear==0) {printf("下溢");exit(-1);}x=Q->data[1];Q->data[1]=Q->data[Q->rear--];i=1;j=2*i;while (j<=Q->rear){if (j<Q->rear&&Q->data[j]>Q->data[j+1]) j++;if (Q->data[i]<Q->data[j]) break;else{temp=Q->data[i];Q->data[i]=Q->data[j];Q->data[j]=temp;i=j;j=2*i;}}return x;
}

优先队列的实现

堆的应用

堆排序

堆这个数据结构可以用于排序。只需要用小根堆建立一个优先队列，然后把所有数据入队，依次出列的结果就是所有数据从小到大的排序结果。
我们来计算一下堆排序的算法复杂度。由于入队和出队是对称操作，故只需考虑入队就行了。每次入队的复杂度为当前队列中元素的对数，即若当前队列中有i个元素，那么当前元素入队时的时间复杂度为O(log2i)O(log_2 i)O(log2​i)。共n个元素，那么入队时总的复杂度为O(∑i=1nlog2i)=O(log2∏i=1ni)=O(log2n!)O(\\sum_{i=1}^n{log_2 i})=O(log_2{\\prod_{i=1}^n{}i})=O(log_2{n!})O(∑i=1n​log2​i)=O(log2​∏i=1n​i)=O(log2​n!)。根据斯特林公式，当n趋于无穷大时，n!≈2πn(ne)nn!\\approx \\sqrt{2\\pi n}(\\frac{n}{e})^nn!≈2πn​(en​)n，可以得到O(log2n!)=O(log22πn(ne)n)=O(log22πn+nlog2ne)=O(nlog2n)O(log_2{n!})=O(log_2{\\sqrt{2\\pi n}(\\frac{n}{e})^n})=O(log_2{\\sqrt{2\\pi n}}+nlog_2{\\frac{n}{e}})=O(nlog_2{n})O(log2​n!)=O(log2​2πn​(en​)n)=O(log2​2πn​+nlog2​en​)=O(nlog2​n)
于是得到堆排序的时间复杂度为O(nlog2n)O(nlog_2{n})O(nlog2​n)。
代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
#define Maxsize 100
typedef int DataType;
typedef struct
{DataType data[Maxsize];int rear;
} PriQueue;
void EnQueue(PriQueue *Q,DataType x)
{int i,temp;if (Q->rear==Maxsize-1) {printf("上溢");exit(-1);}Q->rear++;i=Q->rear;Q->data[i]=x;while(i/2>0&&Q->data[i/2]>x){temp=Q->data[i];Q->data[i]=Q->data[i/2];Q->data[i/2]=temp;i=i/2;}
}
DataType DeQueue(PriQueue *Q)
{int i,j,x,temp;if (Q->rear==0) {printf("下溢");exit(-1);}x=Q->data[1];Q->data[1]=Q->data[Q->rear--];i=1;j=2*i;while (j<=Q->rear){if (j<Q->rear&&Q->data[j]>Q->data[j+1]) j++;if (Q->data[i]<Q->data[j]) break;else{temp=Q->data[i];Q->data[i]=Q->data[j];Q->data[j]=temp;i=j;j=2*i;}}return x;
}
int main()
{int n,x;PriQueue Q;Q.rear=0;cin>>n;for (int i=1;i<=n;i++){cin>>x;EnQueue(&Q,x);}for (int i=1;i<=n;i++){cout<<DeQueue(&Q)<<' ';}
} 

这其实不是标准的堆排序写法。标准的堆排序建堆的复杂度是$O(n)$，但总的复杂度仍为O(nlog2n)O(nlog_2{n})O(nlog2​n)。我这种直接采用优先队列入队操作来建堆的写法实现起来比较简单，又不影响时间复杂度。

TOP-K问题

什么是TOP-K问题

给定n个数据，求前K个最大（最小）的元素。
比如求专业前10名，世界500强等，都属于TOP-K问题。

TOP-K问题的排序解法

有一种很简单的解法，即排完序之后输出前K个元素。一般来说，现有的最好的排序算法复杂度为O(nlog2n)O(nlog_2{n})O(nlog2​n)，那么这样做的复杂度就也是O(nlog2n)O(nlog_2{n})O(nlog2​n)。一般这个问题中n都特别大，而K比较小。所以我们可以改进一下这个算法。

TOP-K问题的堆解法

假设要求最大的K个元素。我们可以建立一个小根堆，保持堆中的元素始终为K个。这个堆表示的含义是当前元素中，最大的K个元素。先把前K个元素加入堆中，然后一个一个考虑后面的元素：若该元素比小根堆的堆顶大，就删除根结点，然后把当前元素插入堆中。通过这个操作，始终可以保证堆中的元素一定是当前考虑过的所有元素中最大的K个。代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
#define Maxsize 100
typedef int DataType;
typedef struct
{DataType data[Maxsize];int rear;
} PriQueue;
void EnQueue(PriQueue *Q,DataType x)
{int i,temp;if (Q->rear==Maxsize-1) {printf("上溢");exit(-1);}Q->rear++;i=Q->rear;Q->data[i]=x;while(i/2>0&&Q->data[i/2]>x){temp=Q->data[i];Q->data[i]=Q->data[i/2];Q->data[i/2]=temp;i=i/2;}
}
DataType DeQueue(PriQueue *Q)
{int i,j,x,temp;if (Q->rear==0) {printf("下溢");exit(-1);}x=Q->data[1];Q->data[1]=Q->data[Q->rear--];i=1;j=2*i;while (j<=Q->rear){if (j<Q->rear&&Q->data[j]>Q->data[j+1]) j++;if (Q->data[i]<Q->data[j]) break;else{temp=Q->data[i];Q->data[i]=Q->data[j];Q->data[j]=temp;i=j;j=2*i;}}return x;
}
int main()
{int n,k,x;PriQueue Q;Q.rear=0;cin>>n>>k;for (int i=1;i<=k;i++){cin>>x;EnQueue(&Q,x);}for (int i=k+1;i<=n;i++){cin>>x;if (x>Q.data[1]){DeQueue(&Q);EnQueue(&Q,x);}}int a[k+1];for (int i=1;i<=k;i++) a[k+1-i]=DeQueue(&Q);for (int i=1;i<=k;i++) cout<<a[i]<<' ';
} 

由于堆的大小为K，所以这个算法的时间为O(nlog2K)O(nlog_2 K)O(nlog2​K)。在n较大，K较小时，这个算法还是比一般算法要快不少的。

总结

本文主要介绍了堆和优先队列的概念、具体实现及其应用。堆和优先队列在各个领域中有着广泛的应用。