一、基本概念
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （largest-in，first-out）的行为特征。
抽象数据类型：
优先队列的接口同前面讲到的队列的接口一样，是其基于泛型的API接口代码如下：
public interface Queue<E> { //队列是否为空 boolean isEmpty(); //队列的大小 int size(); //入队 void enQueue(E element); //出队 E deQueue(); }
二、基于数组实现的优先队列
实现优先队列最简的方法就是基于前面讲到的基于数组的栈的代码，只需对插入或删除操作作相应的更改即可。
1、基于有序数组的实现
在栈的代码的插入方法中添加代码，将所有较大的元素向右移动一格，以保证数组有序（和插入排序相同），这里我们可以使用二分查找的方法来找出元素应插入的位置，然后再移动元素。这样最大元素，总是在数组的最右边，其删除操作和栈的实现中一样。
代码：
/** * 基于有序数组的实现的优先队列 * @author Alent * @param <E> */ public class PriorityQueue<E extends Comparable<E>> implements Queue<E>{ private E[] elements; private int size=0; @SuppressWarnings("unchecked") public PriorityQueue() { elements = (E[])new Comparable[1]; } @Override public int size() {return size;} @Override public boolean isEmpty() {return size == 0;} @Override public void enQueue(E element) { if(size == elements.length) { resizingArray(2*size);//若数组已满将长度加倍 } elements[size++] = element; insertSort(elements); } @Override public E deQueue() { E element = elements[--size]; elements[size] = null; //注意：避免对象游离 if(size > 0 && size == elements.length/4) { resizingArray(elements.length/2);//小于数组1/4,将数组减半 } return element; } //插入排序，由于前面n-1个元素是有序的，这里只插入最后一个元素 public void insertSort(E[] a) { int N = size -1; //最后一个元素是size-1，不是a.length-1 if(N == 0) return; int num = binaryFind(a, a[N], 0, N-1); E temp = a[N]; //num后的元素向后移动 for (int j = N; j > num; j--) { a[j] = a[j-1]; } a[num] = temp; } //找出元素应在数组中插入的位置 public int binaryFind(E[] a, E temp, int down, int up) { if(up<down || up>a.length || down<0) { System.out.println("下标错误"); } if(temp.compareTo(a[down]) < 0) return down; if(temp.compareTo(a[up]) > 0) return up+1; int mid = (up-down)/2 + down; if(temp.compareTo(a[mid]) == 0) { return mid + 1; }else if(temp.compareTo(a[mid])<0) { up = mid-1; }else if(temp.compareTo(a[mid])>0) { down = mid+1; } return binaryFind(a,temp,down,up); } //交换两个元素 public void swap(E[] a,int i,int j) { E temp = a[i]; a[i] = a[j]; a[j] = temp; } //调整数组大小 public void resizingArray(int num) { @SuppressWarnings("unchecked") E[] temp = (E[])new Comparable[num]; for(int i=0;i<size;i++) { temp[i] = elements[i]; } elements = temp; } public static void main(String[] args) { int[] a = {4,2,1,3,8,new Integer(5),7,6};//测试数组 PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); System.out.print("入栈顺序："); for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); pq.enQueue(a[i]); } System.out.println(); System.out.print("出栈顺序数组实现："); while(!pq.isEmpty()) { System.out.println(pq.deQueue()); } } }
2、基于无序数组的实现
同样，我们一个可以在删除方法中修改，在删除方法中添加一段类似于选择排序内循环的代码，每次删除时先找出数组中的最大元素，然后与最右边元素进行交换，然后在删除元素。
代码：
@Override public void enQueue(E element) { if(size == elements.length) { resizingArray(2*size);//若数组已满将长度加倍 } elements[size++] = element; } @Override public E deQueue() { swapMax(elements); E element = elements[--size]; elements[size] = null; //注意：避免对象游离 if(size > 0 && size == elements.length/4) { resizingArray(elements.length/2);//小于数组1/4,将数组减半 } return element; } public void swapMax(E[] a) { int max = size -1; for(int i=0;i<size-1; i++) { if(larger(a[i],a[max])) max = i; } swap(a, size-1, max); } //比较两个元素大小 public boolean larger(E a1, E a2) { return a1.compareTo(a2)>0; }
三、基于堆实现的优先队列
基本概念：
当一个二叉树的每个结点都大于等于它的两个子结点时，我们称它是堆有序的。根结点是堆有序的二叉树的最大结点。
二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储。
一棵堆有序的完全二叉树
为了操作方便，这是我们使用一个数组，来表示一个堆。我们不使用数组的第一个元素，具体实现在《数据结构与算法（四），树》中有提及，这里就不说了。
1、堆的有序化
当我们将元素插入到堆（数组的末尾）中时，插入的元素可能比它的父结点要大，堆的有序状态被打破。我们需要交换它和它的父节点来修堆，直到堆重新变为有序状态。其操作如下图：
代码如下：
//上浮操作 private void swim(int k) { while(k > 1 && less(k/2, k)) { swap(k/2, k); k = k/2; } } private boolean less(int i, int j) { return elements[i].compareTo(elements[j]) < 0; } //交换两个元素 public void swap(int i,int j) { E temp = elements[i]; elements[i] = elements[j]; elements[j] = temp;
同样的，当我们从堆中删除根结点并将它的最后一个元素放到顶端时，堆的有序性被打破，我们需要将它与它的两个子结点种的较大者进行交换，以恢复堆的有序性，其操作流程如下图：
其代码如下：
//下沉操作 private void sink(int k) { while(2*k <= size) { int j = 2*k; if(j < size && less(j, j+1)) j++; if(!less(k,j)) break; swap(k,j); k = j; } }
2、基于堆实现的优先队列
基于堆的优先队列的实现代码如下：
/** * 基于堆的优先队列 * @author Alent */ public class MaxPQ<E extends Comparable<E>> implements Queue<E>{ private E[] elements; private int size=0; @SuppressWarnings("unchecked") public MaxPQ(int capacity) { elements = (E[])new Comparable[capacity + 1]; } @Override public int size() {return size;} @Override public boolean isEmpty() {return size == 0;} @Override public void enQueue(E element) { elements[++size] = element; swim(size); } //上浮 private void swim(int k) { while(k > 1 && less(k/2, k)) { swap(k/2, k); k = k/2; } } private boolean less(int i, int j) { return elements[i].compareTo(elements[j]) < 0; } @Override public E deQueue() { E result = elements[1]; swap(1, size--); elements[size + 1] = null; sink(1); return result; } //下沉 private void sink(int k) { while(2*k <= size) { int j = 2*k; if(j < size && less(j, j+1)) j++; if(!less(k,j)) break; swap(k,j); k = j; } } //交换两个元素 public void swap(int i,int j) { E temp = elements[i]; elements[i] = elements[j]; elements[j] = temp; } }
三种实现方法的时间复杂度比较：
四、索引优先队列
索引优先队列，它用一个索引数组保存了某个元素在优先队列中的位置，使得我们能够引用已经进入优先队列中的元素。最在些应用中，通常是很有必要的，如：有向图的Dijkstra算法中就使用了索引优先队列，来返回最小边的索引。
其实现方法为：
使用elements[]数组来保存队列中的元素，pq[]数组用来保存elements中元素的索引，在添加一个数组qp[]来保存pq[]的逆序——qp[i]的值是i在pq[]中的位置（即 pq[qp[i]] = i）。若i不在队列中，则令qp[i] = -1。辅助函数less()、swap()、sink()、swim()和前面优先队列中的一样。
索引优先队列的代码实现：
/** * 基于堆实现的索引优先队列 */ public class IndexMinPQ<E extends Comparable<E>>{ private int[] pq; //索引二叉堆 private int[] qp; // 保存逆序：pq[qp[i]] = i; private E[] elements; //元素 private int size = 0; @SuppressWarnings("unchecked") public IndexMinPQ(int capacity) { elements = (E[]) new Comparable[capacity + 1]; pq = new int[capacity + 1]; qp = new int[capacity + 1]; for (int i = 0; i <= capacity; i++) { qp[i] = -1; } } public boolean isEmpty() { return size == 0; } //删除最小元素，并返回索引 public int delMin() { int index = pq[1]; swap(1, size--); sink(1); elements[pq[size + 1]] = null; qp[pq[size + 1]] = -1; return index; } //删除索引k及其元素 public void delete(int k) { int index = qp[k]; swap(index, size--); swim(index); sink(index); elements[k] = null; qp[k] = -1; } //插入元素，将它和索引k关联 public void insert(int k, E element) { size++; qp[k] = size; pq[size] = k; elements[k] = element; swim(size); } //改变索引k关联的元素 public void change(int k, E element) { elements[k] = element; swim(qp[k]); sink(qp[k]); } //是否包含索引k public boolean contains(int k) { return qp[k] != -1; } //下沉 private void sink(int k) { while (2 * k <= size) { int j = 2 * k; if (j < size && less(j, j + 1)) j++; if (!less(k, j)) break; swap(k, j); k = j; } } //上浮 private void swim(int k) { while (k > 1 && less(k / 2, k)) { swap(k, k / 2); k = k / 2; } } private boolean less(int i, int j) { return elements[pq[i]].compareTo(elements[pq[j]]) > 0; } //交换两元素 private void swap(int i, int j) { int swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; qp[pq[i]] = i; qp[pq[j]] = j; } }
索引优先队列的时间复杂度：
