1，堆作為優先級隊列的應用
對於普通隊列而言，具有的性質為FIFO，只要實現在隊頭刪除元素，在隊尾插入元素即可。因此，這種隊列的優先級可視為按 時間到達 的順序來衡量優先級的。到達得越早，優先級越高，就優先出隊列被調度。
更一般地，很多應用不能單純地按時間的先後來分優先級，比如按CPU占用時間或者其它方式……在這種情形下，使用堆更容易表達優先級隊列。
2，堆的兩個性質：①結構性質--堆從結構上看是一顆完全二叉樹。然而，從物理存儲上看，堆的實現基本上是使用一個一維數組存儲堆中所有的結點。②ordering property---這是由堆的定義決定的，如大頂堆：根結點的值要大於左右孩子的值。
由於堆具有這兩個性質，故在對堆進行操作時，如插入操作、刪除操作……都需要維護好這兩個性質，因此：這也是為什麼堆的插入、刪除操作經常需要進行向上調整和向下調整，這就是為了維護堆的 ordering property。
3，建堆時間復雜度的分析
在數據結構--堆的實現(上)中，分析了建堆的兩種方法，時間復雜度一種為O（nlogn)，一種為O(n)。現在仔細分析如下：
1 import java.io.File;
2 import java.io.FileNotFoundException;
3 import java.util.Scanner;
4
5 public class Sort {
6 public static void main(String[] args) throws FileNotFoundException{
7 Scanner sc = new Scanner(new File("inputfile"));//read heap's element from inputfile
8 int n = sc.nextInt();//first line in the file gives number of integers to be read
9 ArrayMaxHeap<Integer> sortHeap = new ArrayMaxHeap<Integer>(n);
10 //build heap
11 for(int i = 0; i < n; i++)
12 sortHeap.add(sc.nextInt());//O(nlogn)
13
14 //sort phase
15 while(!sortHeap.isEmpty())
16 System.out.println(sortHeap.removeMax());
17 }
18 }
在上面for循環中的建堆操作中，添加堆中的第一個元素時，完全二叉樹高度為1，調用add方法進行堆調整的最壞情況需要 Log1 時間。添加第二個元素時，完全二叉樹高度為2，進行堆調整的最壞情況需要 log2 時間……添加第 i 個元素時，最壞需要 logi 時間進行堆調整。故將 n 個元素添加到堆中需要時間：
log1 + log2 + log3 + …… + log(n-1) + logn = log(1*2*3……*n) = log n!
n! = (n/e)nsqrt(2n*pi)
故 O(logn!) = O(nlogn)
同理，也可分析下 while 循環中的堆排序。removeMax()的時間復雜度為logn，n為當前堆中元素的個數。故堆排序的時間復雜度為O(nlogn)
從這裡可以看出，此種建堆的方法是調用堆定義的接口來實現的。即調用 堆的接口add()來實現。
另一種建堆的方式則是直接操作堆的底層存儲---一維數組 來建堆。此方法建堆的時間復雜度為O(n)
1 Integer[] arr = new Integer[4];arr[0] = 20;arr[1] = 40;arr[2] = 30;arr[3] = 10;
2 ArrayMaxHeap<Integer> heap2 = new ArrayMaxHeap<Integer>(arr);
3
4 public ArrayMaxHeap(T[] entries){
5 heap = (T[]) new Comparable[entries.length + 1];//how to use generic array...
6 lastIndex = entries.length;
7 for(int index = 0; index < entries.length; index++)
8 {
9 heap[index + 1] = entries[index];//第0號位置不存放元素
10 System.out.println(heap[index + 1]);
11 }
12 for(int index = lastIndex / 2; index >= 1; index--)
13 reheap(index);//從最後一個非葉結點到根結點調用reheap進行堆調整操作
14 }
在第12行的for循環中，從最後一個非葉結點(lastIndex/2)開始，直接調用reheap()操作Integer數組。
private void reheap(int rootIndex){
boolean done = false;//標記堆調整是否完成
T orphan = heap[rootIndex];
int largeChildIndex = 2 * rootIndex;//默認左孩子的值較大
//堆調整基於以largeChildIndex為根的子樹進行
while(!done && (largeChildIndex <= lastIndex)){
//largeChildIndex 標記rootIndex的左右孩子中較大的孩子
int leftChildIndex = largeChildIndex;//默認左孩子的值較大
int rightChildIndex = leftChildIndex + 1;
//右孩子也存在,比較左右孩子
if(rightChildIndex <= lastIndex && (heap[largeChildIndex].compareTo(heap[rightChildIndex] )< 0))
largeChildIndex = rightChildIndex;
if(orphan.compareTo(heap[largeChildIndex]) < 0){
heap[rootIndex] = heap[largeChildIndex];
rootIndex = largeChildIndex;
largeChildIndex = 2 * rootIndex;//總是默認左孩子的值較大
}
else//以rootIndex為根的子樹已經構成堆了
done = true;
}
heap[rootIndex] = orphan;
}
reheap的偽代碼如下：
input:array A[0...n-1]
output: max heap in A[0...n-1]
x = n/2 - 1
while(x>=0)
v=value at x
siftdown(v)
x=x-1
endwhile
時間復雜度為O(n)的分析：
假設堆的高度為 h，當reheap某個結點時，需要對 以該結點為根 的子樹進行向下的調整。向下調整時根結點有兩次比較（與左右孩子的比較）。
因此，假設某結點在第 i 層，0<= i <h，該結點一共需要 2(h-i)次比較。（最後一層葉結點是不需要比較的，因為建堆是從非葉結點開始）
由於是完全二叉樹，故第 i 層的結點個數為 2i
總比較次數為：除去最後一層葉子結點外，其它層的所有的結點的比較次數之和.設總比較次數為S
因此，終於明白這種建堆方法的時間復雜度為O(n)了。
參考：數據結構--堆的實現(上)
