优先队列是特殊的“队列”，取出元素的顺序是依据优先权（关键字）的大小，而不是依据进入队列的先后顺序。
对于实现优先队列的存储，数组的插入操作效率比较低，我们考虑使用树。首先想到了二叉树，但多次的删除最值操作可能导致树的不平衡，也会导致效率变低，而完全二叉树平衡性好，并且存储方便，我们可以使用完全二叉树来存储。这里引入堆（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 }