java實現算法之堆排序
堆排序與快速排序，歸并排序一樣都是時間復雜度為O(N*logN)的幾種常見排序方法。學習堆排序前，先講解下什么是數據結構中的二叉堆。
二叉堆的定義
二叉堆是完全二叉樹或者是近似完全二叉樹。
二叉堆滿足二個特性：
1．父結點的鍵值總是大于或等于（小于或等于）任何一個子節點的鍵值。
2．每個結點的左子樹和右子樹都是一個二叉堆（都是最大堆或最小堆）。
當父結點的鍵值總是大于或等于任何一個子節點的鍵值時為最大堆。當父結點的鍵值總是小于或等于任何一個子節點的鍵值時為最小堆。下圖展示一個最小堆：
由于其它幾種堆（二項式堆，斐波納契堆等）用的較少，一般將二叉堆就簡稱為堆。
堆的存儲
一般都用數組來表示堆，i結點的父結點下標就為(i – 1) / 2。它的左右子結點下標分別為2 * i + 1和2 * i + 2。如第0個結點左右子結點下標分別為1和2。
堆的操作——插入刪除
下面先給出《數據結構C++語言描述》中最小堆的建立插入刪除的圖解，再給出本人的實現代碼，最好是先看明白圖后再去看代碼。
堆的插入
每次插入都是將新數據放在數組最后。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，現在的任務是將這個新數據插入到這個有序數據中——這就類似于 直接插入排序 中將一個數據并入到有序區間中， 代碼：
/**
* 新加入i結點 其父結點為(i - 1) / 2
* 新插入的節點都是位於數組末尾，從該節點開始檢查，類似“上浮”的過程
* @param a
* @param i
*/
static void minHeapFixup (int[] a, int i) {
int j, temp;
temp = a[i];
j = (i - 1) / 2;//父節點
while (j > 0 && i != 0) {
if (a[j] <= temp) {
break;
}
a[i] = a[j]; //把較大的子結點往下移動,替換它的子結點
i = j;
j = (i - 1) / 2;
}
a[i] = temp;
}
插入時：
//在最小堆中插入元素時
static void minHeapAddNumber(int[] a, int n, int value) {
a[n] = value;
minHeapFixup(a, n);
}
堆的刪除
按定義，堆中每次都只能刪除第0個數據。為了便于重建堆，實際的操作是將最后一個數據的值賦給根結點，然后再從根結點開始進行一次從上向下的調整。調整時先在左右兒子結點中找最小的，如果父結點比這個最小的子結點還小說明不需要調整了，反之將父結點和它交換后再考慮后面的結點。相當于從根結點將一個數據的“下沉”過程。下面給出代碼：
// 從i節點開始調整,n為節點總數 從0開始計算 。i節點的子節點為 2*i+1, 2*i+2。刪除的調整過程有點類似“下沉”過程
static void minHeapFixdown(int[] a, int i, int n) {
int temp = a[i];
int j = 2 * i + 1;//左兒子
while (j < n) {
if (j + 1 < n && a[j] > a[j + 1]) {//選出兩個孩子中較小的孩子
j++;
}
if (a[j] >= temp) {
break;
}
a[i] = a[j]; //把較小的子結點往上移動,替換它的父結點
i = j;
j = 2 * i + 1;
}
a[i] = temp;
}
/**
* 刪除小頂堆，是刪除第一個元素，用最后的元素填充到第一個元素。
* 其實，也就是第一個與最后一個元素交換，然后長度縮短一個就可以實現。
* 小頂堆采取這種方式排序出來，最后得到的是從大到小的逆序。因為每次都將最小的交換到最后。
* @param a
* @param first
* @param n
*/
static void minHeapDeleteNumber(int a[], int n) {
int temp = a[0];
a[0] = a[n - 1];
a[n - 1] = temp;
minHeapFixdown(a, 0, n - 1);
}
堆化數組
有了堆的插入和刪除后，再考慮下如何對一個數據進行堆化操作。要一個一個的從數組中取出數據來建立堆吧，不用！先看一個數組，如下圖：
很明顯，對葉子結點來說，可以認為它已經是一個合法的堆了即20，60， 65， 4， 49都分別是一個合法的堆。只要從A[4]=50開始向下調整就可以了。然后再取A[3]=30，A[2] = 17，A[1] = 12，A[0] = 9分別作一次向下調整操作就可以了。下圖展示了這些步驟：
寫出堆化數組的代碼：
/**
* 數組元素來生成小頂堆，從第n/2 - 1個元素開始，因為葉子元素已是合法的堆了
* @param a
* @param n
*/
static void makeMinHeap(int[] a, int n) {
for (int j = n / 2 - 1; j >= 0 ; j--) {
minHeapFixdown(a, j, n);
}
}
至此，堆的操作就全部完成了(注1)，再來看下如何用堆這種數據結構來進行排序。
堆排序
首先可以看到堆建好之后堆中第0個數據是堆中最小的數據。取出這個數據再執行下堆的刪除操作。這樣堆中第0個數據又是堆中最小的數據，重復上述步驟直至堆中只有一個數據時就直接取出這個數據。
由于堆也是用數組模擬的，故堆化數組后，第一次將A[0]與A[n - 1]交換，再對A[0…n-2]重新恢復堆。第二次將A[0]與A[n – 2]交換，再對A[0…n - 3]重新恢復堆，重復這樣的操作直到A[0]與A[1]交換。由于每次都是將最小的數據并入到后面的有序區間，故操作完成后整個數組就有序了。有點類似于直接選擇排序。
//堆排序，小頂堆，排序形成的是逆序的數組，過程就是交換第一個和最后一個元素，每次數組長度減少1
static void minheapSortToDescendArray(int[] a, int n) {
int temp;
for (int j = n - 1; j >= 0; j--) {
//交換
temp = a[0];
a[0] = a[j];
a[j] = temp;
//調整
minHeapFixdown(a, 0, j);
}
}
注意使用最小堆排序后是遞減數組，要得到遞增數組，可以使用最大堆。
由于每次重新恢復堆的時間復雜度為O(logN)，共N - 1次重新恢復堆操作，再加上前面建立堆時N / 2次向下調整，每次調整時間復雜度也為O(logN)。二次操作時間相加還是O(N * logN)。故堆排序的時間復雜度為O(N * logN)。
完整的實現代碼如下：
package Algorithm.ylh.com;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] a = GenerateIntArray.getArray();
System.out.println(Arrays.toString(a));
makeMinHeap(a, a.length);//建堆
System.out.println(Arrays.toString(a));
minHeapDeleteNumber(a, a.length);//刪除一個元素
System.out.println(Arrays.toString(a));
minHeapAddNumber(a, a.length - 1, 20);//添加一個元素
System.out.println(Arrays.toString(a));
minheapSortToDescendArray(a, a.length);//排序
System.out.println(Arrays.toString(a));
}
/**
* 新加入i結點 其父結點為(i - 1) / 2
* 新插入的節點都是位於數組末尾，從該節點開始檢查，類似“上浮”的過程
* @param a
* @param i
*/
static void minHeapFixup (int[] a, int i) {
int j, temp;
temp = a[i];
j = (i - 1) / 2;//父節點
while (j > 0 && i != 0) {
if (a[j] <= temp) {
break;
}
a[i] = a[j]; //把較大的子結點往下移動,替換它的子結點
i = j;
j = (i - 1) / 2;
}
a[i] = temp;
}
//在最小堆中插入元素時
static void minHeapAddNumber(int[] a, int n, int value) {
a[n] = value;
minHeapFixup(a, n);
}
// 從i節點開始調整,n為節點總數 從0開始計算 。i節點的子節點為 2*i+1, 2*i+2。刪除的調整過程有點類似“下沉”過程
static void minHeapFixdown(int[] a, int i, int n) {
int temp = a[i];
int j = 2 * i + 1;//左兒子
while (j < n) {
if (j + 1 < n && a[j] > a[j + 1]) {//選出兩個孩子中較小的孩子
j++;
}
if (a[j] >= temp) {
break;
}
a[i] = a[j]; //把較小的子結點往上移動,替換它的父結點
i = j;
j = 2 * i + 1;
}
a[i] = temp;
}
/**
* 刪除小頂堆，是刪除第一個元素，用最后的元素填充到第一個元素。
* 其實，也就是第一個與最后一個元素交換，然后長度縮短一個就可以實現。
* 小頂堆采取這種方式排序出來，最后得到的是從大到小的逆序。因為每次都將最小的交換到最后。
* @param a
* @param first
* @param n
*/
static void minHeapDeleteNumber(int a[], int n) {
int temp = a[0];
a[0] = a[n - 1];
a[n - 1] = temp;
minHeapFixdown(a, 0, n - 1);
}
/**
* 數組元素來生成小頂堆，從第n/2 - 1個元素開始，因為葉子元素已是合法的堆了
* @param a
* @param n
*/
static void makeMinHeap(int[] a, int n) {
for (int j = n / 2 - 1; j >= 0 ; j--) {
minHeapFixdown(a, j, n);
}
}
//堆排序，小頂堆，排序形成的是逆序的數組，過程就是交換第一個和最后一個元素，每次數組長度減少1
static void minheapSortToDescendArray(int[] a, int n) {
int temp;
for (int j = n - 1; j >= 0; j--) {
//交換
temp = a[0];
a[0] = a[j];
a[j] = temp;
//調整
minHeapFixdown(a, 0, j);
}
}
}
來源： http://blog.csdn.net/rebirth_love/article/details/51347109http://blog.csdn.net/rebirth_love/article/details/51347109