一.优先队列: 能够完成下列操作的数据结构叫做优先队列：1.插入一个数值 2.取出最小值/最大值,并删除.
二.堆: 使用二叉树可以高效实现上述两种操作,把它称为堆.
堆的性质:1.儿子一定不小于父亲的值. 2数的节点按照从上到下,从左到右的顺序排列,即完全二叉树
插入操作:在堆的末尾插入一个数,然后不断向上提升直到没有大小颠倒为止.
删除操作(最小值):把最后一个节点的数值复制到根节点,并删除最后一个节点(size - 1).再把数调整到标准形式.
两种操作时间复杂度:O(logn)
1 #include <cstdio>; 2 3 const int MAXSIZE = 1000; 4 int heap[MAXSIZE], sz = 0; 5 void push(int x);//向堆中插入数值 6 int pop();//取出堆中的最小值,并删除 7 8 int main() 9 { 10 //测试 11 return 0; 12 } 13 void push(int x) 14 { 15 int i = sz++; 16 while (i > 0) { 17 int p = (i - 1) / 2; 18 if (heap[p] <= x) break; 19 heap[i] = heap[p]; 20 i = p; 21 } 22 heap[i] = x; 23 } 24 int pop() 25 { 26 int ret = heap[0]; 27 int x = heap[--sz]; 28 int i = 0; 29 while (i * 2 + 1 < sz) { 30 int a = i * 2 + 1, b = i * 2 + 2; 31 if (b < sz && heap[b] < heap[a]) a = b; 32 if (heap[a] >= x) break; 33 heap[i] = heap[a]; 34 i = a; 35 } 36 heap[i] = x; 37 return ret; 38 }
原文：http://www.cnblogs.com/WJZDMR/p/3577292.html