优先队列

前面我们说过，队列是先进先出，优先队列也是一个队列，但它的特点是进可以正常进，但是出就要按照优先级出，优先级可以是最大值、最小值，也可以是按照特定的值出（如：元素出现的次数等等）。

优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。

优先队列的实现机制

一般在面试中，会问你知不知道优先队列的实现机制，但不需要你动手写，所以我们要做的是了解它内部的实现机制。因为优先队列在不同的语言中，已经纳入到标准库里面，很多版本的实现你直接用即可。

简单来说，有两种实现机制：

• 用堆（heap）来实现，比如二叉堆、斐波那契堆等；
• 用二叉搜索树来实现；

二叉搜索树会在后面讲二叉树时再详解，这里主要说一下二叉堆。

二叉堆

一个二叉堆的形式如上图所示，这里以最小堆为例。图中二叉堆的父节点永远都比左右子节点要小，这样转换到优先队列中就是每次取二叉堆中的最顶层父节点的值（它就是这个队列中的最小值），所以它的查询操作的时间复杂度是O(1)，而在插入或删除操作时，由于每次操作完都要重新维护二叉堆的顺序，也就是要把最小值放到顶部，它的时间复杂度是O(logN)。

堆也分很多种类，在Wikipedia)中可以看到这样的图。它给出了不同的堆之间的一些对比。这个图是我们需要去记住的。

to be continue…