这里是最小堆，最大堆也是类似的。
1.堆是一颗完全二叉树。
性质：儿子节点的值一定不小于父节点的值。
堆的存储用一个数组heap[n]即可。
由于完全二叉树的性质，节点是按顺序排列的，
i 节点的子节点编号为 2*i+1 和 2*i+2 。
同理 i 节点的父节点为 (i-1)/2 。
操作：堆有插入和删除两种操作，由于是二叉树，两种操作都是O(logn) 的 。
实现C++代码：
#include <bitsstdc++.h> using namespace std; #define MAX_N 1000 int heap[MAX_N],sz = 0; void push(int x){ //新加入节点的编号 int i = sz++; while(i > 0){ //父节点 int p = (i-1)/2; //如果新加节点小于它的父节点，则退出 if(heap[p] <= x) break; //把父节点放下来 heap[i] = heap[p]; //把自己提上去 i = p; } //循环退出的时候已经找到了该放的位置 // 把新节点加入进来 heap[i] = x; } int pop(){ //有值才能pop assert(sz > 0); //要删除的元素 int ret = heap[0]; //记录最后一个节点的值 int x = heap[--sz]; //找到最后一个节点该待的位置,因为最后一个节点已经被删除了 int i = 0; //如果有子节点就循环 while(i * 2 + 1 < sz){ //找到较小的子节点 int a = i*2+1; int b = i*2+2; if(b < sz&&heap[b] < heap[a]) a = b; //如果较小的子节点大于最后一个节点的值则退出，因为已经找到了最后一个节点该待的位置 if(heap[a] >= x) break; //把子节点提上来 heap[i] = heap[a]; //进入子节点 i = a; } //把最后一个节点放到它该待的位置 heap[i] = x; return ret; } int main(){ }