在很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。
在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue) 。
本文首先介绍优先级队列的定义，有序和无序数组以及堆数据结构实现优先级队列，最后介绍了基于优先级队列的堆排序(Heap Sort)
更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
一 定义
优先级队列和通常的栈和队列一样，只不过里面的每一个元素都有一个”优先级”，在处理的时候，首先处理优先级最高的。如果两个元素具有相同的优先级，则按照他们插入到队列中的先后顺序处理。
优先级队列可以通过链表，数组，堆或者其他数据结构实现。
二 实现
数组
最简单的优先级队列可以通过有序或者无序数组来实现，当要获取最大值的时候，对数组进行查找返回即可。代码实现起来也比较简单，这里就不列出来了。
如上图：
· 如果使用无序数组，那么每一次插入的时候，直接在数组末尾插入即可，时间复杂度为O(1)，但是如果要获取最大值，或者最小值返回的话，则需要进行查找，这时时间复杂度为O(n)。
· 如果使用有序数组，那么每一次插入的时候，通过插入排序将元素放到正确的位置，时间复杂度为O(n)，但是如果要获取最大值的话，由于元阿苏已经有序，直接返回数组末尾的 元素即可，所以时间复杂度为O(1).
所以采用普通的数组或者链表实现，无法使得插入和排序都达到比较好的时间复杂度。所以我们需要采用新的数据结构来实现。下面就开始介绍如何采用二叉堆(binary heap)来实现优先级队列
二叉堆
二叉堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 有了这一性质，那么二叉堆上最大值就是根节点了。
二叉堆的表现形式：我们可以使用数组的索引来表示元素在二叉堆中的位置。
从二叉堆中，我们可以得出：
· 元素k的父节点所在的位置为[k/2]
· 元素k的子节点所在的位置为2k和2k+1
跟据以上规则，我们可以使用二维数组的索引来表示二叉堆。通过二叉堆，我们可以实现插入和删除最大值都达到O(nlogn)的时间复杂度。
对于堆来说，最大元素已经位于根节点，那么删除操作就是移除并返回根节点元素，这时候二叉堆就需要重新排列；当插入新的元素的时候，也需要重新排列二叉堆以满足二叉堆的定义。现在就来看这两种操作。
从下至上的重新建堆操作: 如果一个节点的值大于其父节点的值，那么该节点就需要上移，一直到满足该节点大于其两个子节点，而小于其根节点为止，从而达到使整个堆实现二叉堆的要求。
由上图可以看到，我们只需要将该元素k和其父元素k/2进行比较，如果比父元素大，则交换，然后迭代，一直到比父元素小为止。