优先队列（Priority Queue)

　　优先队列是特殊的“队列”，取出元素的顺序是依据优先权（关键字）的大小，而不是依据进入队列的先后顺序。

　　对于实现优先队列的存储，数组的插入操作效率比较低，我们考虑使用树。首先想到了二叉树，但多次的删除最值操作可能导致树的不平衡，也会导致效率变低，而完全二叉树平衡性好，并且存储方便，我们可以使用完全二叉树来存储。这里引入堆（Heap）的概念：

　　堆（Heap):堆是一颗具有特定性质的二叉树，堆的基本要求就是堆中所有结点的值必须大于或等于（或小于或等于）其孩子结点的值，这也称为堆的性质；堆还有另一个性质，就是当 h > 0 时，所有叶子结点都处于第 h 或 h - 1 层（其中 h 为树的高度），也就是说，堆应该是一颗完全二叉树；

　　我们可以用堆来实现优先队列。

　　优先队列的完全二叉树表示中有以下特性：

　　1.用数组表示完全二叉树，对于存储在a[ i ]中的节点，其左儿子a[ 2*i ]，右儿子a[ 2*i+1 ]，父节点a[ i/2 ]  ；

　　2.任一结点是其子树所有结点关键字的最大值（最小值同理）。

一、插入

　　首先将待插入结点放在数组最后，即作为最后一个树的叶子节点，再不断调整至合适位置。操作为：与父节点比较大小，如果大于父节点，则将父节点移到当前位置，待插入节点的位置坐标更新；如果比父节点小，则当前位置就是合适的位置。

 1 const int MAX=1e5;
 2 int size=1;
 3 int queue[MAX];
 4 
 5 void insert(int x)
 6 {
 7     if(size==MAX-1) return;
 8     queue[++size]=x;
 9     int temp=size;
10     for( ；temp>1&&queue[temp/2]<x ; temp/=2)
11     {
12         queue[temp]=queue[temp/2];
13     }
14     queue[temp]=x;
15 }

二、删除

　　根节点就是最值，删除时返回根节点，将最后一个叶子节点放置根节点位置，再进行位置调整。操作为：当前待调整位置的节点与左右儿子中的最大值进行比较，如果比这个最大值小，则将较大节点与父节点进行交换；如果大于这个最值，则不再需要调整。

 1 int delete_()
 2 {
 3     int max=queue[1];
 4     int x=queue[size--];
 5     int temp=1;
 6     for( ;temp*2<=size; temp*=2)
 7     {
 8         int big=temp*2;
 9         if( temp*2<size && queue[big+1]>queue[big] ) big++;
10 
11         if( queue[big]<x ) break;
12         else
13         {
14             queue[temp]=queue[big];
15         }
16     }
17     queue[temp]=x;
　　　　return max;
18 }

三、创建堆

　　即考虑如何将N个数放在堆中。首先我们想到将元素不断插入到初始为空堆里的方法，这样的时间复杂度为O（nlogn)。其实还有更快的时间复杂度为O（n）的方法，步骤为：

 　　1.顺序读入N个数，将其存放在数组里，满足完全二叉树的结构

　　 2.从下往上调整，建立堆

　　一个堆的根节点的左子树和右子树一定是堆，而最小的堆是只有一个节点的叶子节点，于是我们可以从叶子节点的父节点开始调整建堆。

 1 void down(int p)
 2 {
 3     int x=queue[p];
 4     int temp=p;
 5     for( ;temp*2<=size; temp*=2)
 6     {
 7         int big=temp*2;
 8         if( temp*2<size && queue[big+1]>queue[big] ) big++;
 9 
10         if( queue[big]<x ) break;
11         else
12         {
13             queue[temp]=queue[big];
14         }
15     }
16     queue[temp]=x;
17 }
18 void creat(int n)
19 {
20     for(int i=1;i<=n;i++) cin>>queue[i];
21     size=n;
22     for(int j=n/2;j>0;j--)
23     {
24         down(j);
25     }
26 }