前面讲了最大最小堆，现在来讲下最大最小堆的用途——实现优先级队列
复习一下：前面讲的最大最小堆的生成，是把一个数组转换成完全二叉树之后，才转换成最大最小堆的。然后生成的时候先从最下方的叶结点开始生成最大/最小堆。
但是优先级队列的话，往往是原本没有任务在里面，然后再往里面一个个添加任务。这怎么实现呢？
我们分析可以知道，当我们向数组的最后一位添加一个元素的时候，就相当于在一个最大/最小堆上加了一个元素。由于原本的就是最大/最小堆，我们只需要处理好当前插入的元素，使插入后仍然满足最大/最小堆的性质就可以了。
那么怎么从优先级队列中取出元素呢？
我们知道，优先级队列中，最高优先级的是堆顶的元素。当我们把堆顶的元素删除之后，要使得剩下的部分仍能够组成一个最大/最小堆，那怎么办呢？
分析之后可以发现，其实就是要找一个元素来替换掉原来堆顶元素的位置。从剩下的元素里寻找，发现，只有移动下标最大的那个元素才能够使得其它部分都不会受到牵连。于是我们就把下标最大的那个元素移动到堆顶。然后，由于剩下的部分都是满足最大最小堆的性质，只需要递归地找到这个堆顶元素应该处在哪个位置，就能使得整个完全二叉树满足最大/最小堆的性质。
题目是这样子的：
题目编号为ALDS1_9_C
来自 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C
代码语言：javascript复制Priority Queue
A priority queue is a data structure which maintains a set S of elements, each of with an associated value (key), and supports the following operations:
insert(S,k): insert an element k into the set S
extractMax(S): remove and return the element of S with the largest key
Write a program which performs the insert(S,k) and extractMax(S) operations to a priority queue S. The priority queue manages a set of integers, which are also keys for the priority.
Input
Multiple operations to the priority queue S are given. Each operation is given by "insert k", "extract" or "end" in a line. Here, k represents an integer element to be inserted to the priority queue.
The input ends with "end" operation.
Output
For each "extract" operation, print the element extracted from the priority queue S in a line.
Constraints
The number of operations ≤2,000,000
0≤k≤2,000,000,000样例输入
代码语言：javascript复制insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end样例输出
代码语言：javascript复制8
10
11
2按照上面的思路，我们就能写出以下的代码
代码语言：javascript复制#include<iostream>
using namespace std;
#define MAX 2000000
#define INFTY (1<<30)
int A[MAX 1], H = 0;
int parent(int i)
{
return i / 2;
}
int left(int i)
{
return 2 * i;
}
int right(int i)
{
return 2 * i 1;
}
void increaseKey(int i, int key)
{
if (key < A[i])
return;
A[i] = key;
while (i > 1 && A[parent(i)] < A[i])
{
swap(A[parent(i)], A[i]);
i = parent(i);
}
}
void ins(int k)
{
H ;
A[H] = -INFTY;
increaseKey(H, k);
}
void maxHeapify(int i)
{
int L = left(i);
int R = right(i);
int P = parent(i);
int largest;
if (L <= H && A[L] > A[i]) largest = L;
else largest = i;
if (R <= H && A[R] > A[largest])
largest = R;
if (largest != i)
{
swap(A[i], A[largest]);
maxHeapify(largest);
}
}
void ext()
{
if (H < 1)
return;
int maxv = A[1];
A[1] = A[H];
A[H] = -INFTY;
H--;
maxHeapify(1);
cout << maxv << endl;
}
int main()
{
string cmd = "";
int num;
cin >> cmd;
while (cmd != "end")
{
if (cmd[0] == 'i')
{
cin >> num;
ins(num);
}
else ext();
cin >> cmd;
}
}通过标准库来实现队列
众所周知，STL非常的强大，我们可以通过STL来实现优先级队列。
前面介绍过stack（基于LIFO的容器），queue（基于FIFO的容器）。现在这里有个priority_queue，可以实现优先级队列。
如果要实现最大堆那样子的优先级队列的话，在定义的时候只要这样写就可以了：
代码语言：javascript复制priority_queue<int>PQ;但是要实现最小堆的话，就要这样子写了：
代码语言：javascript复制priority_queue<int,vector<int>,greater<int>> b;//从小到大priority_queue的操作和queue相同，push()用于向队列中插入一个元素。pop()用于删除队列首部的一个元素。top()用于访问队列首部的元素。
下面用一段例程演示了priority_queue是如何工作的：
代码语言：javascript复制#include<iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int>PQ;
PQ.push(1);
PQ.push(8);
PQ.push(3);
PQ.push(5);
cout<<PQ.top()<<endl;
PQ.pop();
cout<<PQ.top()<<endl;
PQ.pop();
PQ.push(11);
cout<<PQ.top()<<endl;
PQ.pop();
cout<<PQ.top()<<endl;
PQ.pop();
cout<<"---------我是分割线-------"<<endl;
priority_queue<int,vector<int>,greater<int>> b;//从小到大
b.push(1);
b.push(8);
b.push(3);
b.push(5);
cout<<b.top()<<endl;
b.pop();
cout<<b.top()<<endl;
b.pop();
b.push(0);
cout<<b.top()<<endl;
b.pop();
cout<<b.top()<<endl;
b.pop();
}用priority_queue来实现上面的题目
当我们使用priority_queue来实现上面的题目的时候，就会发现，代码量少了很多！
代码语言：javascript复制#include<iostream>
#include<queue>
#include<string>
using namespace std;
int main()
{
priority_queue<int> q;
string cmd="";
int tmp;
cin>>cmd;
while(cmd!="end")
{
if(cmd[0]=='i')
{
cin>>tmp;
q.push(tmp);
}
else
{
cout<<q.top()<<endl;
q.pop();
}
cin>>cmd;
}
}
