- 索引優(yōu)先隊列
在很多應用中渔伯，允許用例引用已經進入優(yōu)先隊列中的元素是很有必要的糯俗。做到這一點的簡單方法是給每個元素一個索引尿褪。另外，一個常見的情況是用例已經有了總量為N的多個元素得湘，而且還可能同時使用了多個數(shù)組來存儲這些元素的信息杖玲。
關聯(lián)索引的泛型優(yōu)先隊列的API
public class IndexMinPQ<Item extends Comparable<Item>>
IndexMinPQ(int maxN) //創(chuàng)建一個最大容量為maxN的優(yōu)先隊列，索引取值范圍為0~maxN-1
void insert(int k, Item item) //插入一個元素淘正，并與索引k關聯(lián)
void change(int k, Item item) //將索引k的元素設為item
boolean contains(int k) //是否存在索引為k的元素
void delete(int k) //刪去索引k及其相關聯(lián)的元素
Item min() //返回最小元素
int minIndex() //返回最小元素索引
int delMin() //刪除最小元素并返回它的索引
boolean isEmpty() //優(yōu)先隊列是否為空
int size() //優(yōu)先隊列的元素數(shù)量
理解這種數(shù)據結構的一個較好的方式是把它看作一個能夠快速訪問其中最小元素的數(shù)組摆马。事實上它還要更好——它可以快速訪問數(shù)組的一個特定子集的最小元素（即所有被插入的元素）。
下面的用例調用了IndexMinPQ的代碼Multiway解決了多向歸并問題：將多個有序的輸入流歸并為一個有序的輸入流鸿吆，且并不需要占用太多的內存囤采。
public class Multiway{
public static void merge(In[] streams){
int N = streams.length;
IndexMinPQ<String> pq = new IndexMinPQ<String>(N);
for(int i=0; i<N; i++){
if(!streams[i].isEmpty())
pq.insert(i, streams[i].readString());
while(!pq.isEmpty()){
StdOut.println(pq.min());
int i = pq.delMin();
if(!streams[i].isEmpty())
pq.insert(i, streams[i].readStrings());
}
}
public static void main(String[] args){
int N = args.length;
In[] streams = new In[N];
for( int i=0; i<N; i++)
streams[i] = new In(args[i]);
merge(streams);
}
}
- 堆排序
堆排序可以分為兩個階段。在堆的構造階段惩淳，我們將原始的數(shù)組重新組織安排進一個堆中蕉毯；然后在下沉排序階段，我們從堆中按遞減的順序取出所有元素并得到排序的結果思犁。
由N個給定的元素構造一個堆代虾，當然可以從左至右的遍歷數(shù)組，用swim保證掃描指針左側的所有元素已經堆有序激蹲，但這樣做的話消耗的時間將與NlogN成正比棉磨，更加高效的辦法是從右至左用sink函數(shù)構造子堆。數(shù)組每個位置都是根結點了学辱，sink()同樣適用于這些子堆乘瓤。因此我們每次都只需要掃描一半的元素，并最后在位置1調用sink()方法项郊。
public static void sort(Comparable[] a){
int N = a.length;
for( int k =N/2; k>=1; k--)
sink(a, k, N);
while(N>1){
exch(a, 1, N--);
sink(a,q,N);
}
}
這段代碼用sink()方法將a[1]到a[N]的元素排序馅扣。for循環(huán)構造了堆，然后用while循環(huán)將最大的元素a[1]和a[N]交換了位置并修復了堆着降，如此重復直至堆變空差油。
