优先队列

优先队列，顾名思义，就是一种根据一定优先级存储和取出数据的队列，是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素它可以说是队列和排序的完美结合体，不仅可以存储数据，还可以将这些数据按照我们设定的规则进行排序。

它的“优先”意指取队首元素时，有一定的选择性，即根据元素的属性选择某一项值最优的出队~。以操作系统对任务队列的处理原理提出来优先队列这个概念，在操作系统对任务的调度中，任务队列并不是简单的FIFO形式，而是以一定的优先级被调用的，这个队列就是优先队列，调度上带有级别区分的队列。

优先队列中至少要存在两种操作：insert和deletemin，前者对应着元素入队，后者对应于出队。 可以以很多方式实现优先队列，比如链表，这样插入操作只需要O(1)的时间，但是删除最小元的时间为O(N),也可以用二叉查找树，这样两种操作的平均运行时间都为O(logN)。 对于优先队列最普遍的实现是：二叉堆。
                 一些优先队列的实现方案的时间性能对比 

 
          

从这张表里我们可以按照时间复杂度这个优先级来进行一次排序，当然，你会选用最后一种二叉查找树作为实现优先队列的方案，但是实际上我们采用的是堆。堆，就是一种二叉树，堆和二叉查找树是类似的，但是也有些许不同：从形状来看，二叉查找树可以有不同的形状，而堆只能是完全二叉树；在时间性能上，二者并无明显的区别。堆也是有序的，我们一般将其分为大顶堆和小顶堆。小顶堆，顾名思义，就是这个堆的子结点的值小于父结点的值；相反的，大顶堆就是堆的子结点的值都大于父结点的值。

在实现的时候，我们常常使用基于数组的堆，即堆中的元素保存在一个数组中，而这个数组元素的保存也是按照一定规律的：如果父结点的位置为n，那么，其对应的左右子结点的位置分别是2n+1和2n+2。也就是说，我们在视觉上（如果用画图形象化表示堆的话）和本质上将堆打扮成两种东西，这样既便于理解，也利于实现，本质的实现是用数组是因为考虑到数组的一些性能。