数据结构中的堆结构

堆（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;
}