什么是堆？
维基百科中对堆的定义如下：
「堆是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的父节点，那么P的值会小于等于（或大于等于）C的值”。若父节点的值恒小于等于子节点的值，此堆称为小顶堆（min heap）；反之，若父节点的值恒大于等于子节点的值，此堆称为大顶堆（max heap）。」
堆中元素的性质
由于堆本质上是一棵完全二叉树，通常是采用数组作为其存储结构，以数组作为其存储结构的好处是，我们可以通过下标索引的方式去访问节点的父节点和孩子节点。
-
对于堆中任意一个节点 i 有：
i的父节点：parent( i ) = floor( (i - 1) / 2 )
i的左孩子：left( i ) = 2 * i + 1
i的右孩子：right( i ) = 2 * i + 2
-
对于一个完全二叉树，我们还可以轻易的找到其最后一个叶子节点：
最后一个叶子节点的下标：floor( ( j - 1 ) / 2 )，其中j是堆中最后一个元素的下标。
堆的操作
创建堆
- 若要向一个空的数组中插入元素来创建堆，首先需将待插入的元素安置在数组的最后一位，再使用shiftup()调整其位置，(以大顶堆为例)若其父节点元素值大于带插入的元素，那么就将其与它的父节点交换
#define MAXN 1000
int heap[MAXN], size = 0;
void shiftup(int start){
int i = start;
while(i >= 0 && heap[i] > heap[(i-1)/2]){
swap(heap[(i-1)/2], heap[i]);
i = (i-1)/2;
}
}
void insert(int x){ //向堆中插入元素
heap[size] = x;
shiftup(size);
size++;
}
- 另一种常见的创建堆的方式是将一个数组堆化(heapify)，从堆的最后一个非叶子节点开始，对每个节点进行shiftdown操作。
void shiftdown(int* arr, int start, int length){
int i = start, j = 2 * i + 1;
while(j < length){
if(j + 1 < length && arr[j + 1] > arr[j])j++;
if(arr[i] > arr[j])break;
swap(arr[j], arr[i]);
i = j;
j = 2 * j + 1;
}
}
void heapify(int* arr, int length){
/**
将一个给定的数组arr转化为大顶堆
时间复杂度：O(n)
*/
int i = (length - 2) / 2;
while(i >= 0)shiftdown(arr, i--, length);
}
删除堆顶元素
将堆顶元素用堆的最后一个元素替代，再使用shiftdown操作
void pop(){
if(size == 0)return;
heap[0] = heap[size - 1];
shiftdown(0);
}
返回堆顶元素
int top(){
if(size == 0){
printf("Empty Heap!\n");
return -1;
}return heap[0];
}
STL优先队列
与通常的队列不同，优先队列中的元素被赋予优先级，当访问队列中的元素时，优先级更高的元素先被访问。通常采用堆数据结构来实现优先队列。幸运的是，在STL中已经有了实现好的优先队列模版，直接调用就可以啦～
#include <functional> //包含greater和less两个优先级函数
#include <queue> //priority_queue的头文件
/*大顶堆*/
priority_queue<int, vector<int>, less<int>>pq_max;
/*小顶堆*/
priority_queue<int, vector<int>, greater<int>>pq_min;
/*优先队列的操作*/
pq.push(); //向队列中插入一个元素
pq.pop(); //删除堆顶的元素
pq.top(); //返回堆顶元素
pq.size(); //返回队列中的元素个数
pq.empty(); //判断队列是否为空
分别向上述两个优先队列中插入元素，并依次弹出元素查看，效果如下：
插入序列：4 5 3 2 98 32 19 25
/*pq_max*/
98 32 25 19 5 4 3 2
/*pq_min*/
2 3 4 5 19 25 32 98
