许多应用程序都需要处理有序的元素，但不一定要求它们全部有序，或是不一定要一次就将它们排序。很多情况下是收集一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素。这种情况下，需要的数据结构支持两种操作：删除最大的元素和插入元素。这种数据结构类型叫优先队列。
这里，优先队列基于二叉堆数据结构实现，用数组保存元素并按照一定条件排序，以实现对数级别的删除和插入操作。
1.API
优先队列是一种抽象数据类型，它表示了一组值和对这些值的操作，抽象层使应用和实现隔离开来。
2.初级实现
1.无序数组实现
优先队列的 insert 方法和下压栈的 push 方法一样。删除最大元素时，遍历数组找出最大元素，和边界元素交换。
2.有序数组实现
插入元素时，将较大的元素向右移一格（和插入排序一样）。这样删除时，就可以直接 pop。
使用链接也是一样的逻辑。
这些实现总有一种操作需要线性级别的时间复杂度。使用二叉堆可以保证操作在对数级别的时间完成。
3.堆的定义
数据结构二叉堆可以很好地实现优先队列地基本操作。在二叉堆数组中，每个元素都要保证大于等于另两个特定位置地元素。同样，这两个位置地元素又至少要大于等于数组中另外两个元素，以此类推。用二叉树表示：
当一棵二叉树的每个结点都大于等于它的两个子节点时，它被成为堆有序。从任意结点向上，都能得到一列非递减的元素；从任意结点向下，都能得到一列非递增的元素。根结点是堆有序的二叉树中最大的结点。
二叉堆表示法
这里使用完全二叉树表示：将二叉树的结点按照层级顺序（从上到下，从左往右）放入数组中，不使用数组的第一个位置（为了方便计算），根结点在位置 1 ，它的子结点在位置 2 和 3，子结点的子结点分别在位置 4，5，6，7，一次类推。
在一个二叉堆中，位置 k 的结点的父节点位置在 k/2，而它的两个子结点在 2k 和 2k + 1。可以通过计算数组的索引而不是指针就可以在树中上下移动。
一棵大小为 N 的完全二叉树的高度为 lgN。
4.堆的算法
用长度为 N+1 的私有数组 pq[ ] 表示一个大小为 N 的堆。
堆在进行插入或删除操作时，会打破堆的状态，需要遍历堆并按照要求将堆的状态恢复。这个过程称为 堆的有序化。
堆的有序化分为两种情况：当某个结点的优先级上升（或在堆底加入一个新的元素）时，需要由下至上恢复堆的顺序；当某个结点的优先级下降（例如将根节点替换为一个较小的元素），需要由上至下恢复堆的顺序。
上浮（由下至上的堆的有序化）
当某个结点比它的父结点更大时，交换它和它的父节点，这个结点交换到它父节点的位置。但有可能比它现在的父节点大，需要继续上浮，直到遇到比它大的父节点。（这里不需要比较这个子结点和同级的另一个子结点，因为另一个子结点比它们的父结点小）
//上浮 private void Swim(int n) { while (n > 1 && Less(n / 2, n)) { Exch(n/2,n); n = n / 2; } }