Max Heap Sort

1. class HeapSortAlgorithm {  
2.       
3.     public void HeapSort(int[] array) {  
4.         int heapSize = array.length;  
5.         for (int i = array.length / 2 - 1; i >= 0; i--) {  
6.             MaxHeapify(array, i, array.length);  
7.         }  
8.           
9.         for (int i = array.length - 1; i > 0; i--) {  
10.             swap(0, i, array);  
11.             heapSize--;  
12.             MaxHeapify(array, 0, heapSize);  
13.         }  
14.     }  
15.       
16.     /// MaxHeapify is to build the max heap from the 'position'  
17.     public void MaxHeapify(int[] array, int position, int heapSize)  
18.     {  
19.         int left = left(position);  
20.         int right = right(position);  
21.         int maxPosition = position;  
22.           
23.         if (left < heapSize && array[left] > array[position]) {  
24.             maxPosition = left;  
25.         }  
26.           
27.         if (right < heapSize && array[right] > array[maxPosition]) {  
28.             maxPosition = right;  
29.         }  
30.           
31.         if (position != maxPosition) {  
32.             swap(position, maxPosition, array);  
33.             MaxHeapify(array, maxPosition, heapSize);  
34.         }  
35.     }  
36.       
37.     /// return the left child position  
38.     public int left(int i)  
39.     {  
40.         return 2 * i + 1;  
41.     }  
42.     /// return the right child position  
43.     public int right(int i)  
44.     {  
45.         return 2 * i + 2;  
46.     }   
47. }  

MaxHeapify的时间复杂度为 O(lgn), 所以整个heap sort的复杂度为：O(n lgn).