数据结构 之 堆结构（优先队列）教程

数据结构中的堆结构

堆（Heap），有时候也是一种优先队列，其实现方式主要还是依托完美二叉树进行调整实现，我们对二叉树结构定义规则如下：

1. 二叉树要是完美二叉树
2. 任意子节点的权值不能比其父节点大（或小）

从而我们可以叫这个数据结构叫堆（heap），并且我们定义堆顶为二叉树的根节点。需要注意的是上面的第 2 个条件可以变化，取决于需要实现的是小顶堆还是大顶堆，实现的方式也非必须为二叉树，可以为多叉树，这里举例为二叉树。

我们可以使用堆结构来进行一些元素大小关系的维护，比如进行排序等，或保持前 k 大（小）的元素等；每个元素插入到堆以后将会按照关系进行排序，比如大顶堆，最大的元素会自动排到堆顶，小顶堆则会将最小的元素排到堆顶，我们可以通过弹出元素进行排序或者维护。

堆操作 之 插入元素

当我们插入一个元素的时候，我们可以在完美二叉树的最下层插入一个新的元素，或者当该层满时开辟新的一层并且插入元素，插入后为了维持堆结构的属性，我们需要开始进行向上调整，操作如下：

1. 与其父节点比较大小，若子节点比父节点大，即交换两个节点
2. 不断重复直到子节点比父节点小或者已经到达堆顶

堆操作 之 弹出元素

当我们弹出一个元素的时候，我们弹出的时堆顶，亦即根节点的元素，此时我们可以把完美二叉树最后一个节点移到根节点，同时，为了维持堆结构的属性，我们此时需要开始进行向下调整，操作如下：

1. 与其两个子节点比较大小，若父节点比子节点小，则于最小的子节点交换；
2. 不断重复知道父节点比子节点大或者已经到达二叉树最底层

代码实现：

为了更方便理解，这里使用 C++ 编写了一个大顶堆的代码，由于主要目的是解释原理，故并没有进行任何的优化，仅供参考：

• #include<iostream>
• #include<cstdio>
• #include<algorithm>
•  
• #define MAX_N 1000
•  
• using namespace std;
•  
• int heap[MAX_N + 5] = {0};
• int cnt = 0;
•  
• void push(int x) {
• heap[cnt++] = x;
• int ind = cnt - 1;
• while(ind && heap[(ind - 1) / 2] < heap[ind]) {
• swap(heap[(ind - 1) / 2], heap[ind]);
• ind = (ind - 1) / 2;
• }
• return ;
• }
•  
• void pop() {
• heap[0] = heap[--cnt];
• int ind = 0;
• while(ind * 2 + 1 <= cnt) {
• int tmp = ind;
• if(heap[tmp] < heap[(ind * 2) + 1]) tmp = (ind * 2) + 1;
• if((ind * 2) + 2 <= cnt && heap[tmp] < heap[(ind * 2) + 2]) tmp = (ind * 2) + 2;
• if(tmp == ind) break;
• swap(heap[tmp], heap[ind]);
• ind = tmp;
• }
• }
•  
• int top() {return heap[0];}
• int size() {return cnt;}
•  
• void output() {
• printf("heap: ");
• for(int i = 0; i < cnt; i++) printf("%d ", heap[i]);
• printf("\n");
• return ;
• }
•  
• int main() {
• int a = 0, x;
• cin>>a;
• while(a != -1) {
• switch(a) {
• case 0:{
• cin>>x;
• push(x);
• output();
• }
• break;
• case 1:{
• printf("Pop: %d\n", top());
• pop();
• output();
• }
• break;
• case 2:{
• output();
• }
• break;
• }
• cin>>a;
• }
• return 0;
• }