优先队列从名字我们就可以猜到，其与队列之间存在一定的练习，优先队列与队列一样主要是入队和出队两个操作。但是优先队列与队列的不同之处在于，优先队列会将优先级高的先出队，这在很多情况下非常有用。例如，Windows的MFC是基于消息的响应的机制，内部管理着一个消息队列，计算机不断从消息队列中抓取消息进行响应，那么系统的消息和应用软件的消息优先级必然不同，我们需要优先响应系统的消息，那么优先队列就显示它强大的功能。
堆的实现我们可以通过一个表，或者一个二叉树都可以实现。如果通过一个表实现，入队很方便，但是出队，必须遍历一遍表找到优先级最高的那个，需要花费O(N)的时间，效率太低。对于二叉树来说入队和出队都是O(logN)的时间复杂度，但是二叉树的频繁删除会导致树向右边倾斜，当然我们可以通过平衡树来解决这个问题，但是对于优先队列来说最简单的方式是通过二叉堆实现。
二叉堆的实质是一个数组，只是我们用完全二叉树的形式将其表述出来，完全二叉树与不完全二叉树的区别如下图：
数组的第一位我们空出来是为了去满足二叉堆的性质：设某元素所处于数组中的位置为i，那么他的左儿子的位置使2*i，他的父元素的位置在i/2；
因为对于堆来说插入比删除要频繁，因此将优先级最高的放在第一个，因为删除比插入麻烦的多。
以下是例程，用vector实现：
1 /************************************************************************/ 2 /* 堆的实现 */ 3 /************************************************************************/ 4 #include5 namespace stl 6 { 7 template 8 class Heap 9 {10 public:11 /************************************************************************/12 /*构造函数*/13 Heap(int capacity = 100)14 :size(0) //堆中包含数据个数15 {16 H.resize(capacity);17 }18 19 ~Heap()20 {21 }22 23 bool isEmpty()24 {25 return size == 0;26 }27 28 void makeEmpty()29 {30 size = 0;31 for (auto it = H.begin(); it != H.end(); it++)32 {33 H.erase(it);34 }35 }36 /************************************************************************/37 /*插入函数 */38 void insert(const T & x)39 {40 //如果vector中已经存满了，重新分为大小，数组首地址不存数据41 if (size == H.size() -1)42 {43 H.resize(2*size);44 }45 //size大小加一46 for (int current = ++size; current > 1 && H[current/2] > x; current /= 2)47 {48 H[current] = H[current/2];49 }50 //找到空位将x插入51 H[current] = x;52 }53 54 /*删除函数*/55 T deleteMin()56 {57 if (isEmpty())58 {59 throw();60 }61 int current, child;62 T returnVal = H[1];63 T lastElement = H[size--]; //将最后一个值保存下来，删除一个元素所以自减运算64 for (current = 1; 2 * current > size; current = child)65 {66 child = 2 * current;67 //防止访问越界68 if (child != size && H[2 * current] > H[2 * current + 1]) 69 {70 ++child;71 }72 //比较子较小的儿子与最后一个值的大小，如果儿子较小用儿子上滤，否则跳出循环73 if (H[child] < lastElement)74 {75 H[current] = H[child];76 }77 else78 {79 break;80 }81 }82 H[current] = lastElement;83 return returnVal;84 }85 86 private:87 std::vector H;88 int size;89 };90 }