算法描述：许多应用程序都需要按照顺序处理任务，但是不一定要求他们全部有序，或是不一定要一次就将他们排序。很多情况下我们只需要处理当前最紧急或拥有最高优先级的任务就可以了。面对这样的需求，优先队列算法是一个不错的选择。
算法图示：
算法解释：上图所展示的是最大优先队列（大顶堆）的算法逻辑，在这个标准的二叉树中，任意节点的元素都大于其叶子节点的元素。利用数组表示该二叉树即Array[2]和Array[3]是Array[1]的叶子节点，Array[4]和Array[5]是Array[2]的叶子节点，Array[6]和Array[7]是Array[3]的叶子节点，以此类推。通过计算可知，有任意节点K，K/2是它的根节点，2*K和2*K+1是它的叶子节点。（注：Array[0]通常不使用）。于是对于任意节点的调整可以通过上浮（swim）或下称（sink）来达到目的。
当有新的元素插入的时候，我们会首先把它分配在数组的尾部（Array[size+1]），然后自下而上的根据子节点到根节点的路径不断上浮到合适的位置。
当最大的元素被取走以后，我们会首先把数组尾部Array[size]）的元素放到数组的头部（Array[1]），然后自上而下的从根节点下称到子节点的合适位置。
数组和二叉树互换的算法图例：
Java代码示例：
package algorithms.sorting.pq; import algorithms.common.ArraysGenerator; /** * 最大优先队列（大顶堆） * @param <T> */ public class MaxPriorityQueue<T extends Comparable<T>> { private T[] heap; private int size = 0; public MaxPriorityQueue(int maxSize) { heap = (T[]) new Comparable[maxSize + 1]; } /** * 判单是否为空 * @return {@code true}当前队列未空 * {@code false}否则不为空 */ public boolean isEmpty() { return size == 0; } /** * 插入新元素至末尾，并上浮至合适的位置 * @param value */ public void insert(T value) { heap[++size] = value; swim(size); } /** * 移除堆顶元素并调整堆 * @return T 返回最大元素 */ public T remove() { T maxValue = heap[1]; // 堆顶的元素和堆底元素交换位置，并减少数组长度 exch(1, size--); heap[size + 1] = null; sink(1); return maxValue; } // 元素上浮 private void swim(int k) { // 下层元素如果大于上层元素且该元素非顶层元素时，循环上浮 while (k > 1 && heap[k / 2].compareTo(heap[k]) < 0) { exch(k / 2, k); k = k / 2; } } private void sink(int k) { while (2 * k <= size) { int leafIndex = 2 * k; // 选择两个子节点中更大的那个元素作为交换目标 if (leafIndex < size && heap[leafIndex].compareTo(heap[leafIndex + 1]) < 0) { leafIndex++; } if (heap[k].compareTo(heap[leafIndex]) < 0) { exch(k, leafIndex); } else { // 如果本轮比较未发生元素交换则不用继续下沉 break; } k = leafIndex; } } private void exch(int i, int j) { T tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; } @Override public String toString() { StringBuffer buffer = new StringBuffer(); buffer.append("["); for (int i = 1; i <= size; ++i) { buffer.append(heap[i]); buffer.append(","); } return buffer.deleteCharAt(buffer.length() - 1).append("]").toString(); } public static void main(String[] args) { MaxPriorityQueue maxPriorityQueue = new MaxPriorityQueue(100); Integer[] array = ArraysGenerator.generate(10, 1, 100); for (int i = 0; i < 10; ++i) { maxPriorityQueue.insert(array[i]); } System.out.println(maxPriorityQueue); while(!maxPriorityQueue.isEmpty()) { System.out.println(maxPriorityQueue.remove()); } } }