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)了。
參考:數據結構--堆的實現(上)