很多应用要求我们把元素按顺序排列，但不一定是完整且严格的顺序，也不一定一次就排好。有时候，我们收集一些元素，找出他们中最大的那一个，然后再收集一些元素，找出此刻最大的一个。这时候，一个符合条件的数据结构应该支持下列两种操作：删除（找出）最大的元素，插入元素。这样的数据结构叫做 优先队列。
下面主要介绍优先队列的朴素实现和基于完全二叉树实现(heap based)，以及在后者基础上产生的一种排序算法——堆排序（heapsort）
当然，也有相应的支持删除最小元素操作的优先队列 MinPQ
API
Class MaxPQ :
MaxPQ() # create a priority queue
MaxPQ(int max) # create a priority queue of initial capacity max
MaxPQ(Key[] a) # create a priority queue from the keys in a[]
void insert(Key v) # insert a key into the priority queue
Key max() # return the largest key
Key delMax() # return and remove the largest kay
bool isEmpty() # is the priority queue empty?
int size() # number of keys in the priority queue
设想下面这个情景：给定一个输入，长度为 N ，要求找出前 M 个最大的数。
一种办法是直接对 N 个元素进行排序，然后选出前 M 个大元素即可。但当 N 很大不能一次读入（当然可以把它分成好几次读入，然后再将结果逐一合并排序，不过现在不考虑这些）或输入是一个流时，这种方法便不可行。
另一种办法是：将开始的 M 个元素排好序，然后对于每个新元素，让它和这 M 个元素逐一进行比较。但如果 M 比较大时，这种方法的开销太大。
优先队列的朴素实现（Elementary Implementation）
Array representation (unordered)
这种实现方式基于栈。对于插入操作（insert），用入栈（push）即可实现。对于删除最大元素（remove the maximum）操作，则可以使用类似于选择排序的办法，找出最大的元素，然后将其出栈（pop）。在整个过程中，栈内的元素是无序的，所以是 unordered 的。由于这种方法一直要到非做不可时才进行比较操作，所以称为消极方法（lazy approach）
Array representation (ordered)
这种实现方式基于队列。对于插入操作，将元素插入到队尾，然后依次交换相邻元素，直到新插入的元素到达合适的地方，从而使整个队列始终保持有序（最大元素在队首）。对于删除操作，直接出队就可以（dequeue）。在整个过程中，队列内的元素始终是有序的，所以是 ordered。由于这种方法预先就排好了序，所以称为积极方法（eager approach）
性能比较
| data structure | insert | remove maximum |
|---|---|---|
| ordered array | N | 1 |
| unordered array | 1 | N |
| heap | logN | logN |
| impossible | 1 | 1 |
堆(heap)的定义
一个二叉堆(binary heap)是若干元素的集合，按完全堆有序二叉树来排列，用来表示一个数组中元素的层级关系（不使用数组的第一个元素，即下标为0的）
完全二叉树是二叉树的一种，除了最后一层外，其余各层均填满；最后一层中，所有元素都尽可能地靠近左边，即最右边的一个元素右边没有元素而左边已填满
当一个二叉树的每个节点都大于等于它的子节点（如果有的话）时，称这个二叉树为堆有序的
堆有序的二叉树中最大的元素在树根处
一个大小为 N 的完全二叉树的高度为
二叉堆的实现有链表和数组两种，其中数组实现紧密高效（compact）。将根节点置于数组中下标为1的位置，k 节点的父节点在 处；而 k 节点的子节点（如果有的话）在 2k 和 2k+1 处。我们下面讨论的都是基于数组实现。
基于堆的优先队列
用堆来表示优先队列时，最大的元素在树根处，每个元素都大于等于它的子节点，小于等于它的父节点。当插入或删除元素时，这种顺序便可能被破坏，我们先考虑相应的处理操作（swim 和 sink）来重塑堆的顺序（reheapify），然后用这两种操作来实现优先队列的两个方法（insert 和 remove the maximum)。
当某个节点的优先级增加时（比如一个新节点添加到了堆的底部，实际相当于添加到数组末尾），我们必须向上回溯（travel up），逐一比较，适当地交换元素，来让堆重新有序
当某个节点的优先级降低时（比如用一个小元素替换了原来的根节点的元素），我们必须向下遍历（travel down)，进行比较，适当地交换元素，来让堆重新有序
Bottom-up Reheapify （swim）
当一个元素变得比它父节点大，而破坏了堆顺序时，我们需要交换它与它的父节点，继续向上比较，直到遇到一个比它大的父节点或者到达树根处停止。
void swim (int k)
{
while ( k > 1 && less(k/2, k) # less 函数接收元素在数组中的位置，比较两元素的值, k>1判断是否到达根节点处
{
exch(k/2, k) # exch 函数接收元素在数组中的位置，交换两元素的值
k = k/2 # 整数除法
}
}
Top-down Reheapify (sink)
当一个元素变得比它子节点小，而破坏了堆顺序时，我们需要将它与两个子节点中较大的一个交换，继续向下比较，直到两个子节点都比小于等于它或者到达堆的底部停止。
void sink (int k)
{
while (2*k <= N) # 判断是否到达堆底部
{
int j = 2*k
if (j < N && less(j, j+1)) j++
if (!less(k, j)) break
exch(k, j)
k = j
}
}
Insert
添加一个新的元素到数组末尾，增加堆的大小，然后向上回溯(swim)，重塑堆的顺序(reheapify)
void insert (Key v)
{
pq[++N] = v # pq 为优先队列类的实例，N 为插入元素前数组的大小
swim(N)
}
Remove the maximum
把根节点处的元素从堆中取出，将堆底部（数组末尾）的元素放在根节点处，减少堆的大小，然后向下搜索（sink），重塑堆的顺序（reheapify）
Key delMax()
{
Key max = pq[1]
exch(1, N--)
pq[N+1] = null
sink(1)
return max
}
————————————————————————
一个大小为N的优先队列，基于堆的算法保证了插入操作使用不超过 1 + lgN 次比较，删除最大元素操作使用不超过 2lgN 次比较
————————————————————————
Mutilway heap
当然，可以用堆有序的完全三叉树来表示实现优先队列。这样的话，树的高度比二叉树降低了一些（对数底数变为3），但找出 3 个子节点中最大的却比原来有更高的开销。
索引优先队列（Index priority queue)
在很多应用中，我们需要允许用户找出一个已经在优先队列中的元素。实现这一功能的简单办法就是给每个元素赋一个唯一的整数作为索引。故可以扩展新的方法：
class IndexMinPQ<Item extends Comparable<Item>>:
IndexMinPQ(int maxN) # create a priority queue of capacity maxN
with possible indices between 0 and maxN-1
void insert(int k, Item item) # insert iteml associate it with k
void change(int k, Item item) # change the item associate with k to item
boolean contains(int k) # is k associated with some item?
void delete(int k) # remove k and its associated item
Item min() # return a minimal item
int minIndex() # return a minimal item's index
int delMin() # remove a minimal item and return its index
boolean isEmpty() # is the priority queue empty?
int size() # number of items in the priority queue
————————————————————————
一个大小为N的索引优先队列，对于insert,change priority,delete,remove the minimum操作，都只需要正比于至多 logN 次比较操作
————————————————————————
使用优先队列，可以将多个输入流合并成一个输出流
堆排序（Heapsort）
如何用优先队列实现排序呢？我们把所有元素插入到一个优先队列中，然后依次删除最大的元素，就得到一个排序好的结果。当用朴素的无序数组实现优先队列时，就类似于选择排序；当用朴素的有序数组实现优先队列时，就类似于插入排序。而采用堆实现优先队列时，就得到了一种完全不同的排序算法————称为 堆排序。
堆排序有两个过程：1. 创建堆 2. 从堆中依次取出元素
创建堆 (heap construction)
创建堆有两种方式：
一种是从左到右扫描数组，利用 swim 操作处理每个元素，建立起完整的堆，等价于使用了 N 次插入操作，所以时间复杂度为 NlogN
另一种方法更加高效，利用 sink 操作。由于数组的元素本来就有自己的下标，而我们的目的就是让它们的下标变成堆有序。类似于我们开始就有一个二叉堆，只不过这个堆的元素不是堆有序的，我们需要利用 sink 操作来让他们变得有序。
我们只需要由下自上逐个对父节点进行 sink 操作，保证其子堆的元素顺序是合适的，故整个堆的元素顺序就变得有序了。由于完全二叉树的叶节点数为 (N+1)/2 ♣，那么完全二叉树中父节点数就为 N/2 ♣， 所以只需要从 N/2 处从右向左扫描数组，逐一进行 sink 操作，就可以使整个数组达到堆有序
♣ 除法为整数除法
————————————————————————
一个大小为N的序列，按基于sink的堆排序，需要使用少于 2N 次比较和 N 次交换操作来创建一个堆
————————————————————————
从堆中取出元素（sortdown）
在这个过程中，从堆中取出最大的元素，把它放在数组的空缺位置上（由于数组大小收缩而产生的空位，即交换最大元素与此时下标最大的元素————最后一个元素），最终整个数组就变为有序的了。
如上所属，这个过程重复进行以下两步：
交换最大元素（根节点）和堆的末尾元素（最深层最右边）
删除堆的末尾节点，对根节点进行 sink 操作，使剩下的堆重新有序
直到处理得只剩下根节点为止
// 总的排序算法
void sort(a):
int N = a.length
for (int k = N/2; k >= 1; k--)
sink(a, k, N)
while (N > 1)
{
exch(a, 1, N--)
sink(a, 1, N)
}
————————————————————————
排序N个元素的序列，堆排序使用了少于 2NlgN + 2N 次比较操作和 少于 NlgN + N 次的交换操作
————————————————————————
堆排序的改进
- Sink to the bottom, then swim
在 sortdown 过程中，多数新插入到根节点的元素一般都要向下交换到靠近底层的地方。所以，我们在做 sink 的时候，不再进行两次比较，而是只比较两个子节点的大小，然后交换父节点与较大的子节点。当新插入的节点到达底层时，进行 swim。这样，可以把比较操作的次数降为原来的一半。然而，这个改进只在比较操作的开销大时才有实际意义（比如比较字符串）
堆排序的优缺点
堆排序是一个在时间和空间上都最优的排序算法：在最坏情况下，它使用大约 2NlgN 次比较操作和常数倍的额外空间。
然而，堆排序的缓存性能很差。因为不像其他排序算法，堆排序几乎不比较数组中相邻元素的值。