优先级队列

1,优先级队列是不同于先进先出队列的另一种队列。
最大优先级队列，是这样的一种队列结构，它的内部存放着一系列的元素，每个元素都对应着一个最优级，
最大优先级队列不管各元素的入队顺序，在出队时，总是对应优先级最大的元素出队。

2,优先队列是0个或多个元素的集合,每个元素都有一个优先权或值.
对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.
在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;
在最大优先队列(max priority queue)中,查找操作用来搜索优先权最大的元素,删除操作用来删除该元素.

3,。优先级队列一般分最大优先级队列和最小优先级队列
。这两种优先级队列只是为了适应不同场合的需要而进行区分实现，在算法上来讲没有什么本质的不同.

4,最大优先级队列一般用二叉树来实现。因为考虑到，对于最大优先级队列来讲，我们关心的只是最大值，因此，这时的二叉树只需要具备下面这个性质，那么就可以实现了：
性质A：总是让二叉树中的每一个节点的key（也就是优先级）值比该节点的子节点的key值大。
保持性质A就可以在每次出队操作时，直接取根节点得到最大优先级的元素。然后再进行树结构的调整，使得取出根节点之后，二叉树仍然保持性质A。
这样的二叉树可以保证，每个入队和出队的操作都在O(h)的时间内完成（h是树的高度）

5,考虑到这个树要保证的性质只有性质A，那么可以让这棵二叉树总是保持为完全二叉树（且不破坏性质A），这样树高就会是lgn，那么入队和出队操作的时间复杂度就是O(lgn)。这就比较理想了。

6,对于一棵完全二叉树，我们可以用数组（而不是链表）方式来实现。因为对于数组实现的完全二叉树，index为i的节点，它的父节点的index 是i/2，左子节点的index是i*2，右子节点的index是i*2+1。乘2和除2都是可以通过位移来实现的，效率上很好。而且通过保存元素个数，可以O(1)时间只找到处于树的最未的那个元素。用数组来实现还有一个好处，就是不需要在数据结构中再实现对父、子节点的指针存储，这样也省下了不少空间。这些特点都非常适合（也很好地改善了）优先级队列的实现。