基本思想： 两种操作都跟树的深度成正比，所以复杂度 O(log(n)) ;
push():在向堆中插入数值时，首先在堆的末尾插入该数值，然后不断向上提直到没有大小颠倒为止。
pop(): 从堆中取出一个数值时，首先把堆的最后一个节点的数值复制到根节点上，并且删除最后一个节点，然后不断向下交换直到没有大小颠倒为止，在向下交换的时候，如果有两个儿子，那就选择数值较小的（如果可以交换的话）进行交换。
数组实现：
#include <cstdio>
const int maxn = ;
int heap[maxn], sz=; void push(int x) {
int i = sz++;
while(i > ) {
int p = (i-) / ; //p是父亲节点的编号
if(heap[p] <= x) break; //如果没有大小颠倒则退出
heap[i] = heap[p]; //把父亲节点 放下来 ，而把自己提上去
i = p;
}
heap[i] = x; //把 x放入 正确的位置
} int pop() {
int ret = heap[]; //最小值
int x = heap[--sz]; //要提到根的数值 int i = ; //从根开始向下交换
while(i * + < sz) { //可能 只有 一个 儿子
int a = i * + , b = i * + ; //两个儿子的 编号
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()
{
push();
push();
push();
push();
push(); int x1 = pop();
int x2 = pop(); printf("%d %d\n",x1,x2);
for(int i = ; i< sz; i++)
printf("%d ", heap[i]);
return ;
}
STL：
priority_queue 默认取出的是最大值。
priority_queue<int, vector<int>, greater<int> >que; 从小到大
priority_queue<int, vector<int>, less<int> >que; 从大到小
#include <iostream>
#include <queue>
using namespace std; int main() {
priority_queue<int> que; que.push();
que.push();
que.push(); while(que.size()) {
cout << que.top() << endl;
que.pop();
}
return ;
}