數(shù)據(jù)機構(gòu)與算法--索引優(yōu)先隊列
圖片來自nullzx的博客園
索引優(yōu)先隊列热某，用一個索引數(shù)組保存了元素在數(shù)組中的位置延旧。在插入隊列中時，可看作將一個整數(shù)和一個對象相關(guān)聯(lián)谒府，使得我們可以引用隊列中的元素粗梭。比如在Dijkstra算法中就用到了索引優(yōu)先隊列争便，他將頂點（整數(shù)表示）和源點到該頂點的最短路徑長度關(guān)聯(lián)起來，每次刪除最小元素断医，都能得到與之關(guān)聯(lián)的那個整數(shù)滞乙；如果該整數(shù)已經(jīng)被關(guān)聯(lián)了，還可以更新與該整數(shù)關(guān)聯(lián)的對象鉴嗤≌镀簦可以看出，索引優(yōu)先隊列和優(yōu)先隊列比起來醉锅，操作數(shù)組里面的元素更加方便了——這就是關(guān)聯(lián)了索引帶來的好處兔簇。
我們使用Key[] keys保存對象，int[] pq保存對象在數(shù)組中的位置硬耍，比如pq[1] = 5垄琐，那么keys[pq[1]] = keys[5]表示整數(shù)5和對象關(guān)聯(lián)，而這個整數(shù)5存放于pq索引為1的位置经柴；用一個int[] qp保存pq的逆序狸窘，即如果pq[i] = j（表示數(shù)組pq索引為i的位置存放了一個被關(guān)聯(lián)的整數(shù)j），則有qp[j] = i口锭，因此qp保存的是被關(guān)聯(lián)整數(shù)j在數(shù)組pq中的索引。易知pq[qp[j]] = j; qp[pq[i]] = i
要注意的是介杆，pq數(shù)組存放的關(guān)聯(lián)整數(shù)是連續(xù)的鹃操，而qp和keys數(shù)組中存放的元素不是連續(xù)的，他們的位置是一一對應(yīng)的春哨。如果整數(shù)i還沒有被關(guān)聯(lián)荆隘，總是令qp[i] = -1，因此對應(yīng)地keys[i] = null
自始至終keys數(shù)組中的元素位置不會發(fā)生變化赴背，這就是說所有上浮下沉操作后椰拒，keys中元素的相對位置都不會變化，變化的只是與之關(guān)聯(lián)的索引pq還有qp而已凰荚。（反正都能通過pq數(shù)組中存放的關(guān)聯(lián)整數(shù)快速找到keys數(shù)組中的元素燃观，所以只改變pq和qp中元素的相對位置足矣）
下圖是將與整數(shù)3關(guān)聯(lián)的對象替換成“a”.
這是一個小頂堆，pq是優(yōu)先隊列便瑟，但是它優(yōu)先級的順序并不是按照其關(guān)聯(lián)的整數(shù)來排列的缆毁，而是按照關(guān)聯(lián)整數(shù)對應(yīng)的對象的大小來排列，即keys[pq[i]]到涂。因此可以寫出用于比較兩個元素的less或者greater方法脊框，我們先實現(xiàn)基于小頂堆的索引優(yōu)先隊列颁督，它可以快速找到或者刪除最大元素，所以greater方法如下
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
可以刪除最小元素的IndexMinPQ
我們的所有關(guān)鍵方法幾乎都以greater方法為基礎(chǔ)浇雹，理解它尤為重要沉御。以下是完整實現(xiàn)。
package Chap9;
import java.util.Arrays;
import java.util.NoSuchElementException;
public class IndexMinPQ<Key extends Comparable<Key>> {
private int N;
private int[] pq; // 索引二叉堆昭灵，按照慣例從1開始
private int[] qp; // 逆序吠裆，滿足qp[pq[i]] = pq[qp[i]] = i
private Key[] keys;
public IndexMinPQ(int maxN) {
// 可存放范圍為[0, maxN]
keys = (Key[]) new Comparable[maxN + 1];
// 索引二叉堆,存放范圍為[1, maxN]
pq = new int[maxN + 1];
// 可存放范圍為[0, maxN]
qp = new int[maxN + 1];
// 剛開始沒有關(guān)聯(lián)任何整數(shù)，都設(shè)置為-1
Arrays.fill(qp, -1);
}
// 針對是pq中的索引i虎锚、j硫痰，但是實際引用的是keys中對應(yīng)的元素
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public boolean contains(int k) {
return qp[k] != -1;
}
public void insert(int k, Key key) {
if (!contains(k)) {
N++;
pq[N] = k;
qp[k] = N;
keys[k] = key;
swim(N);
}
}
// 給整數(shù)k重新關(guān)聯(lián)一個對象
public void replace(int k, Key key) {
keys[k] = key;
// 由于和k關(guān)聯(lián)的新key可能大于原來的key（此時需要下沉），也有可能小于原來的key（此時需要上复芑ぁ）效斑，為了簡化代碼，既上浮又下沉柱徙，就囊括了這兩種可能缓屠。
swim(qp[k]);
sink(qp[k]);
}
// 返回最小元素
public Key min() {
return keys[pq[1]];
}
// 最小元素的關(guān)聯(lián)整數(shù)
public int minIndex() {
return pq[1];
}
public int delMin() {
if (isEmpty()) {
throw new NoSuchElementException("隊列已經(jīng)為空，不能執(zhí)行刪除护侮！");
}
int indexOfMin = pq[1];
// 堆頂和最后一個元素交換
swap(1, N--);
sink(1);
// 最后一個元素置為空
keys[indexOfMin] = null;
// 同時關(guān)聯(lián)整數(shù)pq[N]在pq中的的索引設(shè)置為-1敌完，表示還沒有對象與該整數(shù)關(guān)聯(lián)
qp[indexOfMin] = -1;
return indexOfMin;
}
public void delete(int k) {
if (!contains(k)) {
throw new NoSuchElementException("沒有元素與" + k + "關(guān)聯(lián)！");
}
// index為整數(shù)k在pq中的位置
int index = qp[k];
swap(index, N--);
// 這里一定要先上浮下沉后再將元素置空羊初，因為swim方法沒有N的限制滨溉，在沒有交換元素的情況下，即刪除的就是pq中最后一個元素长赞，如果先置空, 會在greater方法中引發(fā)空指針
// 而sink方法有N的限制晦攒，先置空后置空都沒有影響，2k <= N會限制它進(jìn)入循環(huán)得哆，避免了空指針
swim(index);
sink(index);
keys[k] = null;
qp[k] = -1;
}
public Key keyOf(int k) {
if (contains(k)) {
return keys[k];
}
// 沒有與k關(guān)聯(lián)就返回null
return null;
}
private void swap(int i, int j) {
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
// 還要更新qp
qp[pq[i]] = i;
qp[pq[j]] = j;
}
private void swim(int k) {
// k = 1說明當(dāng)前元素浮到了根結(jié)點脯颜，它沒有父結(jié)點可以比較，也不能上浮了贩据，所以k <= 1時候推出循環(huán)
while (k > 1 && greater(k / 2, k)) {
swap(k / 2, k);
// 上浮后栋操，成為父結(jié)點，所以下標(biāo)變成原父結(jié)點
k = k / 2;
}
}
private void sink(int k) {
// 父結(jié)點的位置k最大值為 N/2,若k有左子結(jié)點無右子結(jié)點饱亮，那么2k = N矾芙；若兩個子結(jié)點都有，那么2k + 1 = N
// 有可能位置k只有左子結(jié)點近上，依然要比較蠕啄，用2k + 1 <= N這個的條件不會執(zhí)行比較，所以用2k <= N條件
while (2 * k <= N) {
int j = 2 * k;
// 可以取j = N -1,greater(N -1, N);由于下標(biāo)從1開始，所以pq[N]是有元素的
if (j < N && greater(j, j + 1)) {
// 右子結(jié)點比左子結(jié)點大 歼跟，取右子結(jié)點的下標(biāo)
j++;
}
// 左子結(jié)點或者右子結(jié)點和父結(jié)點比較
// 如果pq[k] >= pq[j]和媳，即父結(jié)點大于等于較大子結(jié)點時，停止下沉
if (!greater(k, j)) {
break;
}
// 否則交換
swap(k, j);
// 下沉后哈街，下標(biāo)變成與之交換的元素下標(biāo)
k = j;
}
}
public static void main(String[] args) {
IndexMinPQ<String> indexMinPQ = new IndexMinPQ<>(20);
indexMinPQ.insert(5, "E");
indexMinPQ.insert(7, "G");
indexMinPQ.insert(2, "B");
indexMinPQ.insert(1, "A");
if (indexMinPQ.contains(7)) {
indexMinPQ.replace(7, "Z");
}
System.out.println(indexMinPQ.min()); // A
System.out.println(indexMinPQ.delMin()); // 1
System.out.println(indexMinPQ.delMin());// 2
System.out.println(indexMinPQ.minIndex()); // 5
System.out.println(indexMinPQ.keyOf(7)); // Z
indexMinPQ.delete(7);
}
}
swap方法不僅交換了pq中的元素——即關(guān)聯(lián)的整數(shù)留瞳，也要同時更新qp，保持qp[pq[i]] = i這樣的關(guān)系骚秦。swim和sink方法沒有改變她倘，要熟知這兩個方法操作的是二叉堆pq，而pq中關(guān)聯(lián)的整數(shù)映射著真正的數(shù)據(jù)元素作箍。因此pq[1]存放的是和最小元素關(guān)聯(lián)的整數(shù)硬梁，通過keys[pq[1]]就可以返回最小元素。這句話解釋了min和minIndex方法的實現(xiàn)胞得。
我們來看insert方法荧止，先判斷要關(guān)聯(lián)的整數(shù)k是不是已經(jīng)被關(guān)聯(lián)了，沒有關(guān)聯(lián)時才能進(jìn)行下面的操作阶剑，和優(yōu)先隊列一樣跃巡，在二叉堆pq的末尾插入，同時qp數(shù)組也要賦值牧愁，然后在keys中的關(guān)聯(lián)整數(shù)k處存入元素素邪，最后上浮操作恢復(fù)堆有序狀態(tài)；如果整數(shù)k已經(jīng)被關(guān)聯(lián)猪半，即replace方法兔朦，用一個新的對象和這個整數(shù)關(guān)聯(lián)，這里注意磨确，由于和k關(guān)聯(lián)的新key可能大于原來的key（此時需要下沉）沽甥，也有可能小于原來的key（此時需要上浮）俐填，為了簡化代碼安接，既上浮又下沉翔忽，就囊括了這兩種可能英融。
delete方法，先找到關(guān)聯(lián)整數(shù)k在pq中的位置歇式，然后將其與最后一個交換位置驶悟，同時N減去1。之后對換過去的元素作上浮下沉操作材失，然后才在keys中將k位置的元素置空痕鳍，一定要先上浮下沉后才置空，因為swim方法沒有N的限制，在沒有交換元素的情況下笼呆，即刪除的就是pq中最后一個元素熊响，如果先置空, 會在greater方法中引發(fā)空指針。
delMin方法刪除最小元素同時返回與之關(guān)聯(lián)的整數(shù)诗赌。最小元素位于堆頂即pq[1]汗茄，這個值就是最小元素關(guān)聯(lián)的整數(shù)。之后刪除最小元素的操作就和delete類似了铭若，將最小元素的索引pq[1]和最后一個元素交換洪碳，然后下沉（在堆頂無需上浮）恢復(fù)堆有序狀態(tài)叼屠。
keyOf(int k)返回與整數(shù)k關(guān)聯(lián)的元素瞳腌。
各個方法在最壞情況下的時間復(fù)雜度如下所示
可以刪除最大元素的IndexMaxPQ
IndexMaxPQ的實現(xiàn)可以通過簡單修改IndexMinPQ得到。將greater方法改成less镜雨，然后實現(xiàn)中所有g(shù)reater方法替換成less即可
private boolean less(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
}
實現(xiàn)如下
package Chap9;
import java.util.Arrays;
import java.util.NoSuchElementException;
public class IndexMaxPQ<Key extends Comparable<Key>> {
private int N;
private int[] pq; // 索引二叉堆嫂侍，按照慣例從1開始
private int[] qp; // 逆序，滿足qp[pq[i]] = pq[qp[i]] = i
private Key[] keys;
public IndexMaxPQ(int maxN) {
// 可存放范圍為[0, maxN]
keys = (Key[]) new Comparable[maxN + 1];
// 索引二叉堆,存放范圍為[1, maxN]
pq = new int[maxN + 1];
// 可存放范圍為[0, maxN]
qp = new int[maxN + 1];
// 剛開始沒有關(guān)聯(lián)任何整數(shù)冷离，都設(shè)置為-1
Arrays.fill(qp, -1);
}
// 針對是pq中的索引i吵冒、j，但是實際引用的是keys中對應(yīng)的元素
private boolean less(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public boolean contains(int k) {
return qp[k] != -1;
}
public void insert(int k, Key key) {
if (!contains(k)) {
N++;
pq[N] = k;
qp[k] = N;
keys[k] = key;
swim(N);
}
}
// 給整數(shù)k重新關(guān)聯(lián)一個對象
public void replace(int k, Key key) {
keys[k] = key;
// 由于和k關(guān)聯(lián)的新key可能大于原來的key（此時需要下沉）西剥，也有可能小于原來的key（此時需要上副云堋），為了簡化代碼瞭空，既上浮又下沉揪阿，就囊括了這兩種可能。
swim(qp[k]);
sink(qp[k]);
}
// 返回最小元素
public Key max() {
return keys[pq[1]];
}
// 最小元素的關(guān)聯(lián)整數(shù)
public int maxIndex() {
return pq[1];
}
public int delMax() {
if (isEmpty()) {
throw new NoSuchElementException("隊列已經(jīng)為空咆畏，不能執(zhí)行刪除南捂！");
}
int indexOfMax = pq[1];
// 堆頂和最后一個元素交換
swap(1, N--);
sink(1);
// 最后一個元素置為空
keys[indexOfMax] = null;
// 同時關(guān)聯(lián)整數(shù)pq[N]在pq中的的索引設(shè)置為-1，表示還沒有對象與該整數(shù)關(guān)聯(lián)
qp[indexOfMax] = -1;
return indexOfMax;
}
public void delete(int k) {
if (!contains(k)) {
throw new NoSuchElementException("沒有元素與" + k + "關(guān)聯(lián)旧找！");
}
// index為整數(shù)k在pq中的位置
int index = qp[k];
swap(index, N--);
// 這里一定要先上浮下沉后再將元素置空溺健，因為swim方法沒有N的限制，在沒有交換元素的情況下钮蛛，即刪除的就是pq中最后一個元素鞭缭，如果先置空, 會在greater方法中引發(fā)空指針
// 而sink方法有N的限制，先置空后置空都沒有影響魏颓，2k <= N會限制它進(jìn)入循環(huán)岭辣，避免了空指針
swim(index);
sink(index);
keys[k] = null;
qp[k] = -1;
}
public Key keyOf(int k) {
if (contains(k)) {
return keys[k];
}
// 沒有與k關(guān)聯(lián)就返回null
return null;
}
private void swap(int i, int j) {
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
// 還要更新qp
qp[pq[i]] = i;
qp[pq[j]] = j;
}
private void swim(int k) {
// k = 1說明當(dāng)前元素浮到了根結(jié)點，它沒有父結(jié)點可以比較甸饱，也不能上浮了沦童，所以k <= 1時候推出循環(huán)
while (k > 1 && less(k / 2, k)) {
swap(k / 2, k);
// 上浮后仑濒，成為父結(jié)點，所以下標(biāo)變成原父結(jié)點
k = k / 2;
}
}
private void sink(int k) {
// 父結(jié)點的位置k最大值為 N/2,若k有左子結(jié)點無右子結(jié)點偷遗，那么2k = N墩瞳；若兩個子結(jié)點都有，那么2k + 1 = N
// 有可能位置k只有左子結(jié)點氏豌，依然要比較矗烛，用2k + 1 <= N這個的條件不會執(zhí)行比較，所以用2k <= N條件
while (2 * k <= N) {
int j = 2 * k;
// 可以取j = N -1,greater(N -1, N);由于下標(biāo)從1開始箩溃，所以pq[N]是有元素的
if (j < N && less(j, j + 1)) {
// 右子結(jié)點比左子結(jié)點大 瞭吃，取右子結(jié)點的下標(biāo)
j++;
}
// 左子結(jié)點或者右子結(jié)點和父結(jié)點比較
// 如果pq[k] >= pq[j]，即父結(jié)點大于等于較大子結(jié)點時涣旨，停止下沉
if (!less(k, j)) {
break;
}
// 否則交換
swap(k, j);
// 下沉后歪架，下標(biāo)變成與之交換的元素下標(biāo)
k = j;
}
}
public static void main(String[] args) {
IndexMaxPQ<String> indexMaxPQ = new IndexMaxPQ<>(20);
indexMaxPQ.insert(5, "E");
indexMaxPQ.insert(7, "G");
indexMaxPQ.insert(2, "B");
indexMaxPQ.insert(1, "A");
if (indexMaxPQ.contains(7)) {
indexMaxPQ.replace(7, "Z");
}
System.out.println(indexMaxPQ.max()); // Z
System.out.println(indexMaxPQ.delMax()); // 7
System.out.println(indexMaxPQ.delMax());// 5
System.out.println(indexMaxPQ.maxIndex()); // 2
System.out.println(indexMaxPQ.keyOf(1)); // A
indexMaxPQ.delete(1);
}
}
使用優(yōu)先隊列的多項歸并
下面的例子使用IndexMinPQ解決了多向歸并的問題：它將多個已經(jīng)有序的輸入流歸并成一個有序的輸出流。無論輸入流有多長霹陡，都可以將其全部讀入并排序（并不是一次性讀入內(nèi)存的和蚪，我們將看到任何時刻隊列中只存在每個輸入流的一個元素而已）
package Chap9;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
public class Multiway {
public static void merge(InputStream[] streams) throws IOException {
int N = streams.length;
// 為每個輸入流關(guān)聯(lián)一個整數(shù)
IndexMinPQ<String> pq = new IndexMinPQ<>(N);
// 從每個流中讀取一個字符，因為每個流都已經(jīng)有序烹棉，所以其中必然有最小元素
for (int i = 0; i < N; i++) {
int ch;
if ((ch=streams[i].read()) != -1) {
pq.insert(i, String.valueOf((char)ch));
}
}
while (!pq.isEmpty()) {
// 不斷選出最小元素打印
System.out.print(pq.min());
// 關(guān)聯(lián)這個整數(shù)的對象被刪除攒霹，從關(guān)聯(lián)該整數(shù)的剩余流中再讀取一個字符，并加入到索引優(yōu)先隊列中
int i = pq.delMin();
int ch;
if ((ch=streams[i].read()) != -1) {
pq.insert(i, String.valueOf((char)ch));
}
}
System.out.println();
}
public static void main(String[] args) {
InputStream stream1 = new ByteArrayInputStream("ACHYZ".getBytes());
InputStream stream2 = new ByteArrayInputStream("BCRXY".getBytes());
InputStream stream3 = new ByteArrayInputStream("ADPQS".getBytes());
InputStream[] streams = {stream1, stream2 ,stream3};
try {
merge(streams); // AABCCDHPQRSXYYZ
} catch (IOException e) {
e.printStackTrace();
}
}
}
上個例子中有三個輸入流浆洗，merge方法剛開始給這三個輸入流分別關(guān)聯(lián)一個整數(shù)催束，然后從這三個輸入流中分別讀取一個字符到索引優(yōu)先隊列中。之后就打印三個字符中的最小者伏社，A被打印然后刪除抠刺，返回與A關(guān)聯(lián)的整數(shù)，然后從與該整數(shù)關(guān)聯(lián)的剩余流中再讀取一個字符摘昌，并加入到索引優(yōu)先隊列中速妖。此時的狀態(tài)又回到每個輸入流的元素都有一個存在于索引優(yōu)先隊列中。隊列中始終保持只有三個元素聪黎，一直選出并刪除最小元素罕容，就完成了多向歸并排序。
運行上面的代碼會輸出AABCCDHPQRSXYYZ稿饰。將三個序列歸并排序成功锦秒！對于任意個輸入流，merge方法都可以應(yīng)對湘纵，并且隊列所需空間和輸入流的個數(shù)成正比脂崔，而不是和所有輸入流的元素個數(shù)成正比滤淳，這可以在歸并排序時節(jié)約大量內(nèi)存梧喷。
by @sunhaiyu
2017.11.7
