1. 基本概念
比如：輸入N個字符串吭狡，我們需要找打最大的M個字符串宅倒。我們可以將N個字符串進(jìn)行排序攘宙，然后取最大的M個。也可以將新的輸入和已知的M個最大字符串進(jìn)行比較戚揭。只要我們用優(yōu)先隊(duì)列能高效的實(shí)現(xiàn)insert()和delMin()就能解決該問題窗宇。
public class TopM {
// This class should not be instantiated.
private TopM() { }
/**
* Reads a sequence of transactions from standard input; takes a
* command-line integer m; prints to standard output the m largest
* transactions in descending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
int m = Integer.parseInt(args[0]);
MinPQ<Transaction> pq = new MinPQ<Transaction>(m+1);
while (StdIn.hasNextLine()) {
// Create an entry from the next line and put on the PQ.
String line = StdIn.readLine();
Transaction transaction = new Transaction(line);
pq.insert(transaction);
// remove minimum if m+1 entries on the PQ
if (pq.size() > m)
pq.delMin();
} // top m entries are on the PQ
// print entries on PQ in reverse order
Stack<Transaction> stack = new Stack<Transaction>();
for (Transaction transaction : pq)
stack.push(transaction);
for (Transaction transaction : stack)
StdOut.println(transaction);
}
}
2. 堆的定義
定義：當(dāng)一顆二叉樹的每個結(jié)點(diǎn)都大于等于它的兩個子結(jié)點(diǎn)時炉媒，它被稱為堆有序。根節(jié)點(diǎn)是堆有序的二叉樹中的最大結(jié)點(diǎn)铺韧。
堆的表示：
①按照樹的層級結(jié)構(gòu)來存儲
②不使用數(shù)組中的第一個位置。
③一顆大小為N的完全二叉樹的高度為lgN向下取整缓淹。當(dāng)N的數(shù)量達(dá)到2的整數(shù)次冪時樹的高度加1
④位置k的結(jié)點(diǎn)的父節(jié)點(diǎn)是? k/2? 哈打，子節(jié)點(diǎn)分別為2k或2k+1
高度=? lg 11 ? 向下取整=3
3. 堆的算法
我們用長度為N+1的pq[]來表示一個大小為N的堆，不使用pq[0]讯壶。
①由下至上的堆有序化（上噶险獭）
某個結(jié)點(diǎn)比自己的父結(jié)點(diǎn)更大，交換它和它的父節(jié)點(diǎn)伏蚊，直到滿足堆有序立轧。
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
②由上至下的堆有序化（下沉）
某個結(jié)點(diǎn)比它的兩個子結(jié)點(diǎn)或是其中之一要小，將它與兩個子節(jié)點(diǎn)中較大的值進(jìn)行交換躏吊，直到保證堆有序氛改。
private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
if (j < n && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
③ 插入元素
將新的元素添加到數(shù)組末尾，增加堆的大小比伏，不斷上浮
④刪除最大的元素
從數(shù)組頂端刪除最大的元素胜卤，并將數(shù)組的最后一個元素放到頂端，減小堆的大小凳怨，并讓這個元素下沉到合適的位置瑰艘。
⑤基于堆的優(yōu)先隊(duì)列
public class MaxPQ<Key extends Comparable<Key>>
{
private Key[] pq; // heap-ordered complete binary tree
private int N = 0; // in pq[1..N] with pq[0] unused
public MaxPQ(int maxN)
{ pq = (Key[]) new Comparable[maxN+1]; }
public boolean isEmpty()
{ return N == 0; }
public int size()
{ return N; }
public void insert(Key v)
{
pq[++N] = v;
swim(N);
}
public Key delMax()
{
Key max = pq[1]; // Retrieve max key from top.
exch(1, N--); // Exchange with last item.
pq[N+1] = null; // Avoid loitering.
sink(1); // Restore heap property.
return max;
}
// See pages 145-147 for implementations of these helper methods.
private boolean less(int i, int j)
private void exch(int i, int j)
private void swim(int k)
private void sink(int k)
}
⑥性能分析
長度為N的基于堆的優(yōu)先隊(duì)列，插入元素操作只需要不超過lgN+1次比較肤舞，刪除最大元素操作紫新，不超過2lgN次比較（確定是否上浮和確定子結(jié)點(diǎn)中的最大值）。
4. 索引優(yōu)先隊(duì)列
可以當(dāng)做：能夠快速訪問其中最小元素的數(shù)組李剖。you can think of an IndexMinPQ named pq as representing a subset of an array pq[0..N-1] of items. Think of the call pq.insert(k, item) as adding k to the subset and setting pq[k] = item and the call pq.change(k, item) as setting pq[k] = item芒率。
問題：多個有序的輸入流如何歸并成一個有序的輸出流？
public class Multiway {
// This class should not be instantiated.
private Multiway() { }
// merge together the sorted input streams and write the sorted result to standard output
private 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());
// Extract and print min and read next from its stream.
while (!pq.isEmpty()) {
StdOut.print(pq.minKey() + " ");
int i = pq.delMin();
if (!streams[i].isEmpty())
pq.insert(i, streams[i].readString());
}
StdOut.println();
}
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);
}
命令行：java Multiway m1.txt m2.txt m3.txt
A A B B B C D E F F G H I I J N P Q Q Z
% more m1.txt
A B C F G I I Z
% more m2.txt
B D H P Q Q
% more m3.txt
A B E F J N
關(guān)鍵：將多路輸入和索引相關(guān)連篙顺，每次都從刪除最小的元素的輸入流中繼續(xù)添加元素偶芍。
5. 堆排序
①堆的構(gòu)造
方法1：構(gòu)造N個元素的堆充择，從左至右依次將每個元素添加至數(shù)組的末尾，然后不斷的上浮匪蟀，直到將N個元素都添加至堆中椎麦。NlgN
方法2：從右至左不斷下沉構(gòu)造堆。
**利用下沉操作構(gòu)建堆只需要2N比較和N交換材彪。
②將堆中最大元素刪除观挎，然后放入堆縮小后數(shù)組中空出的位置
public static void sort(Comparable[] pq) {
int n = pq.length;
for (int k = n/2; k >= 1; k--)
sink(pq, k, n);
while (n > 1) {
exch(pq, 1, n--);
sink(pq, 1, n);
}
}
③分析
將N個元素排序，堆排序只需要少于2NlgN+2N次比較段化，以及一半的交換次數(shù)嘁捷。2N來自于堆的構(gòu)建，2NlgN來自于每次下沉操作最大可能次數(shù)显熏。
堆排序是唯一可以同時利用空間和時間的方法雄嚣，但是許多應(yīng)用中很少使用它，原因是堆排序沒有利用緩存喘蟆，數(shù)組元素很少和相鄰的其他元素進(jìn)行比較缓升，因此緩存未命中的次數(shù)遠(yuǎn)遠(yuǎn)高于其它的算法（快速、歸并履肃、甚至希爾）
