Algorithms4

优先队列

关于优先级的问题，包括最大优先序列（MaxPQ）和最小优先序列（MinPQ）。二叉堆从上往下，MaxPQ从大到小，MinPQ从小到大。

基于堆的优先队列（MaxPQ为例）

使用二叉堆，位置k的节点的父节点位置为k/2」，子节点位置为2k和2k+1，注意：优先队列pq[0]不使用
删除最大元素：将最后面的元素pq[N-1]和pq[1]（最大元素）进行交换，然后将最大元素删去，此时位于pq[1]的元素进行下沉操作；
插入：将新元素放在优先队列的最后面，然后进行上浮操作。

索引优先队列

快速访问其中最小的元素，解决优先队列不能被访问对象的缺点，应用multiway，解决多项归并问题：多个有序输入流归并成一个有序的输出流。
pq：放key的索引，只有它连续；
qp：放key的索引在pq里的位置；
keys：存放键，上浮和下沉操作是判断key的大小，不是pq中key的索引；
注：百度。

堆排序

先使堆有序，在进行下沉排序
使堆有序，只要扫描一半，因为跳过了大小为一的子堆，如果一个结点的两个子结点都已经是堆了，则通过sink变成一个堆。