- 索引优先队列
在很多应用中，允许用例引用已经进入优先队列中的元素是很有必要的。做到这一点的简单方法是给每个元素一个索引。另外，一个常见的情况是用例已经有了总量为N的多个元素，而且还可能同时使用了多个数组来存储这些元素的信息。
关联索引的泛型优先队列的API
public class IndexMinPQ<Item extends Comparable<Item>>
IndexMinPQ(int maxN) //创建一个最大容量为maxN的优先队列，索引取值范围为0~maxN-1
void insert(int k, Item item) //插入一个元素，并与索引k关联
void change(int k, Item item) //将索引k的元素设为item
boolean contains(int k) //是否存在索引为k的元素
void delete(int k) //删去索引k及其相关联的元素
Item min() //返回最小元素
int minIndex() //返回最小元素索引
int delMin() //删除最小元素并返回它的索引
boolean isEmpty() //优先队列是否为空
int size() //优先队列的元素数量
理解这种数据结构的一个较好的方式是把它看作一个能够快速访问其中最小元素的数组。事实上它还要更好——它可以快速访问数组的一个特定子集的最小元素（即所有被插入的元素）。
下面的用例调用了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);
}
}
- 堆排序
堆排序可以分为两个阶段。在堆的构造阶段，我们将原始的数组重新组织安排进一个堆中；然后在下沉排序阶段，我们从堆中按递减的顺序取出所有元素并得到排序的结果。
由N个给定的元素构造一个堆，当然可以从左至右的遍历数组，用swim保证扫描指针左侧的所有元素已经堆有序，但这样做的话消耗的时间将与NlogN成正比，更加高效的办法是从右至左用sink函数构造子堆。数组每个位置都是根结点了，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循环构造了堆，然后用while循环将最大的元素a[1]和a[N]交换了位置并修复了堆，如此重复直至堆变空。
网友评论