這節(jié)總結(jié)一下優(yōu)先隊列的常用實現(xiàn)方法弟跑。
目錄：
1、基本概念
2防症、基于數(shù)組實現(xiàn)的優(yōu)先隊列
2.1孟辑、基于有序數(shù)組的實現(xiàn)
2.2、基于無序數(shù)組的實現(xiàn)
3蔫敲、基于堆實現(xiàn)的優(yōu)先隊列
3.1饲嗽、堆的有序化
3.2、基于堆實現(xiàn)的優(yōu)先隊列
4奈嘿、索引優(yōu)先隊列
1貌虾、基本概念
普通的隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊列尾追加裙犹，而從隊列頭刪除尽狠。在優(yōu)先隊列中衔憨，元素被賦予優(yōu)先級。當(dāng)訪問元素時袄膏，具有最高優(yōu)先級的元素最先刪除践图。優(yōu)先隊列具有最高級先出 （largest-in，first-out）的行為特征沉馆。(百度百科)
抽象數(shù)據(jù)類型：
優(yōu)先隊列的接口同前面講到的隊列的接口一樣码党，是其基于泛型的API接口代碼如下：
public interface Queue<E> {
//隊列是否為空
boolean isEmpty();
//隊列的大小
int size();
//入隊
void enQueue(E element);
//出隊
E deQueue();
}
2、基于數(shù)組實現(xiàn)的優(yōu)先隊列
實現(xiàn)優(yōu)先隊列最簡的方法就是基于前面講到的基于數(shù)組的棧的代碼斥黑，只需對插入或刪除操作作相應(yīng)的更改即可揖盘。
2.1、基于有序數(shù)組的實現(xiàn)
在棧的代碼的插入方法中添加代碼心赶，將所有較大的元素向右移動一格扣讼，以保證數(shù)組有序（和插入排序相同），這里我們可以使用二分查找的方法來找出元素應(yīng)插入的位置缨叫，然后再移動元素椭符。這樣最大元素，總是在數(shù)組的最右邊耻姥，其刪除操作和棧的實現(xiàn)中一樣销钝。
代碼：
/**
* 基于有序數(shù)組的實現(xiàn)的優(yōu)先隊列
* @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);//若數(shù)組已滿將長度加倍
}
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);//小于數(shù)組1/4,將數(shù)組減半
}
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;
}
//找出元素應(yīng)在數(shù)組中插入的位置
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;
}
//調(diào)整數(shù)組大小
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};//測試數(shù)組
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("出棧順序數(shù)組實現(xiàn)：");
while(!pq.isEmpty()) {
System.out.println(pq.deQueue());
}
}
}
2.2、基于無序數(shù)組的實現(xiàn)
同樣婉商，我們一個可以在刪除方法中修改似忧，在刪除方法中添加一段類似于選擇排序內(nèi)循環(huán)的代碼，每次刪除時先找出數(shù)組中的最大元素丈秩，然后與最右邊元素進行交換盯捌，然后在刪除元素。
代碼：
@Override
public void enQueue(E element) {
if(size == elements.length) {
resizingArray(2*size);//若數(shù)組已滿將長度加倍
}
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);//小于數(shù)組1/4,將數(shù)組減半
}
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;
}
3蘑秽、基于堆實現(xiàn)的優(yōu)先隊列
基本概念：
當(dāng)一個二叉樹的每個結(jié)點都大于等于它的兩個子結(jié)點時饺著，我們稱它是堆有序的。根結(jié)點是堆有序的二叉樹的最大結(jié)點肠牲。
二叉堆是一組能夠用堆有序的完全二叉樹排序的元素幼衰，并在數(shù)組中按照層級存儲。
一棵堆有序的完全二叉樹：
為了操作方便缀雳，這是我們使用一個數(shù)組渡嚣，來表示一個堆。我們不使用數(shù)組的第一個元素，具體實現(xiàn)在《數(shù)據(jù)結(jié)構(gòu)與算法（四）严拒，樹》中有提及扬绪，這里就不說了。
3.1裤唠、堆的有序化
當(dāng)我們將元素插入到堆（數(shù)組的末尾）中時，插入的元素可能比它的父結(jié)點要大莹痢，堆的有序狀態(tài)被打破种蘸。我們需要交換它和它的父節(jié)點來修堆，直到堆重新變?yōu)橛行驙顟B(tài)竞膳。其操作如下圖：
代碼如下：
//上浮操作
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;
}
同樣的航瞭，當(dāng)我們從堆中刪除根結(jié)點并將它的最后一個元素放到頂端時，堆的有序性被打破坦辟，我們需要將它與它的兩個子結(jié)點種的較大者進行交換刊侯，以恢復(fù)堆的有序性，其操作流程如下圖：
其代碼如下：
//下沉操作
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;
}
}
3.2锉走、基于堆實現(xiàn)的優(yōu)先隊列
基于堆的優(yōu)先隊列的實現(xiàn)代碼如下：
/**
* 基于堆的優(yōu)先隊列
* @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;
}
}
三種實現(xiàn)方法的時間復(fù)雜度比較：
4滨彻、索引優(yōu)先隊列
索引優(yōu)先隊列，它用一個索引數(shù)組保存了某個元素在優(yōu)先隊列中的位置挪蹭，使得我們能夠引用已經(jīng)進入優(yōu)先隊列中的元素亭饵。最在些應(yīng)用中，通常是很有必要的梁厉，如：有向圖的Dijkstra算法中就使用了索引優(yōu)先隊列辜羊，來返回最小邊的索引。
其實現(xiàn)方法為：
使用elements[]數(shù)組來保存隊列中的元素词顾，pq[]數(shù)組用來保存elements中元素的索引八秃，在添加一個數(shù)組qp[]來保存pq[]的逆序——qp[i]的值是i在pq[]中的位置（即 pq[qp[i]] = i）。若i不在隊列中肉盹，則令qp[i] = -1昔驱。輔助函數(shù)less()、swap()垮媒、sink()舍悯、swim()和前面優(yōu)先隊列中的一樣。
索引優(yōu)先隊列的代碼實現(xiàn)：
/**
* 基于堆實現(xiàn)的索引優(yōu)先隊列
*/
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關(guān)聯(lián)
public void insert(int k, E element) {
size++;
qp[k] = size;
pq[size] = k;
elements[k] = element;
swim(size);
}
//改變索引k關(guān)聯(lián)的元素
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;
}
}
索引優(yōu)先隊列的時間復(fù)雜度：
找出最大元素的索引優(yōu)先隊列的JAVA版本IndexMaxPQ.java 點這里。
好了它抱，這節(jié)就總結(jié)這么多吧秕豫。
