一、準(zhǔn)備知識
1.堆
堆（英語：heap)是計算機科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個可以被看做一棵樹的數(shù)組對象。堆總是滿足下列性質(zhì)：
- 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
- 堆總是一棵完全二叉樹。
將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。
堆是線性數(shù)據(jù)結(jié)構(gòu)，相當(dāng)于一維數(shù)組，有唯一后繼。
堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時，稱之為堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
若將和此次序列對應(yīng)的一維數(shù)組（即以一維數(shù)組作此序列的存儲結(jié)構(gòu)）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不大于（或不小于）其左、右孩子結(jié)點的值。由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。
2.最大堆
把根節(jié)點最大的堆叫最大堆。
二、堆排序的思想
堆排序是將一個數(shù)組通過數(shù)組下標(biāo)關(guān)系虛構(gòu)出一個最大堆，這樣這個最大堆的根節(jié)點是最大的，然后將這個堆的最后一個節(jié)點和根節(jié)點交換，這個最大值就到了數(shù)組的最后，然后數(shù)組的長度減一，減一后的數(shù)組在調(diào)整順序，使其再次成為一個最大堆，這是根節(jié)點就是第二大的元素，然后將重復(fù)上面的步驟，知道全部交換完畢，數(shù)組就排好了順序。
三、排序
1.將數(shù)組構(gòu)造為一個虛擬的最大堆
通過下標(biāo)來構(gòu)造這個最大堆。
（1）數(shù)組下標(biāo)和堆元素的對應(yīng)關(guān)系。
通過上面的圖，我們可以分析出，一個節(jié)點，我們可以使用(n-1)/2來計算它的父節(jié)點的坐標(biāo)、使用2*n+1來計算它的左節(jié)點的坐標(biāo)、使用2*n+2來計算它的右節(jié)點的坐標(biāo)。
（2）構(gòu)造最大堆
遍歷整個數(shù)組，構(gòu)造一個最大堆，每次插入一個數(shù)，然后使堆重新成為一個最大堆。構(gòu)造過程如下：
首先將1加入堆，這時堆中只有一個元素，數(shù)組現(xiàn)在為[1,2,3,4,5,6,7]。
將2加入堆中，計算2的父節(jié)點(1-1)/2=0,2的父節(jié)點是數(shù)組下標(biāo)為0的元素。這時候2成為了1的左節(jié)點，根節(jié)點小于子節(jié)點，不滿足最大堆的定義，所以調(diào)整這個堆，讓根節(jié)點最大，所以1,2交換位置,數(shù)組現(xiàn)在為[2,1,3,4,5,6,7]。
將3加入堆中，計算3的父節(jié)點(2-1)/2=0,3的父節(jié)點是數(shù)組下標(biāo)為0的元素。這時候3成為了2的右節(jié)點，發(fā)現(xiàn)根節(jié)點2小于3，調(diào)整堆，將根節(jié)點2和3交換位置，現(xiàn)在數(shù)組為[3,1,2,4,5,6,7]。
-
重復(fù)上面的步驟，將每一個元素加入這個堆，加入一個節(jié)點后，對比加入的節(jié)點和它的父節(jié)點的大小，如果新加入的節(jié)點大于它的父節(jié)點，則將兩者交換，然后在比較交換后的節(jié)點和它的父節(jié)點的大小，知道使堆重新成為一個最大堆。
構(gòu)造過程代碼：
2. 通過堆的結(jié)構(gòu)調(diào)整來排序。
通過上面的構(gòu)造，我們已將一個數(shù)組通過下標(biāo)關(guān)系構(gòu)造成為了一個虛擬的最大堆，這時候我們知道這個最大堆的根節(jié)點(也就是數(shù)組的第一個元素)現(xiàn)在肯定是所有數(shù)字中最大的一個，然后根據(jù)這個已知關(guān)系調(diào)整這個堆，來達到排序的目的。
調(diào)整過程如下：
將數(shù)組的第一個元素和數(shù)組的最后一個元素交換位置，這樣最大的那個數(shù)就到了數(shù)組的最后，然后數(shù)組長度減一，將最后一個數(shù)排除在外，剩余的數(shù)重新調(diào)整順序，重新成為一個最大堆，這樣根節(jié)點就變成了一個次大的元素。
然后再次將根元素和現(xiàn)在的最后一個元素(原數(shù)組的倒數(shù)第二個元素)交換位置，數(shù)組長度在減一，然后重新調(diào)整堆使其再次成為一個最大堆。
重復(fù)上面的步驟，直到所有的數(shù)字都調(diào)整完畢，這時數(shù)組就排好了順序。
數(shù)組調(diào)整過程：
找出當(dāng)前節(jié)點和它的左節(jié)點、右節(jié)點三者中最大的那個節(jié)點，如果最大的節(jié)點是它自己則不做任何調(diào)整，如果最大的節(jié)點是它的左節(jié)點或者右節(jié)點，則和該節(jié)點交換位置，然后將交換后的節(jié)點作為當(dāng)前節(jié)點在重復(fù)判斷。
重復(fù)上面的步驟，使其重新成為一個最大堆。
調(diào)整過程代碼如下:
四、完整代碼
public class HeapSort {
public void heapSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int heapSize = arr.length;
while (heapSize > 1) {
heapify(arr, --heapSize);
}
}
private void heapInsert(int[] arr,int i) {
int last = (i - 1) / 2; //計算父節(jié)點
while (arr[i] > arr[last]) { // 比較當(dāng)前節(jié)點和父節(jié)點
//調(diào)整堆
swap(arr,i,last);
//繼續(xù)判斷他的上一層節(jié)點是否滿足最大堆
i = last;
last = (i - 1) / 2;
}
}
public void heapify(int[] arr, int heapSize) {
swap(arr, 0, heapSize--);
int cur = 0;
while (2 * cur + 1 <= heapSize) {
int left = 2 * cur + 1;
int right = 2 * cur + 2;
int lastMax = heapSize >= right && arr[left] > arr[right] ?
arr[left] > arr[cur] ? left : cur
: heapSize >= right ?
arr[right] > arr[cur] ? right : cur :
arr[left] > arr[cur]
? left : cur;
if (lastMax == cur) {
break;
}
int temp = arr[cur];
arr[cur] = arr[lastMax];
arr[lastMax] = temp;
cur = lastMax;
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
@Test
public void test() {
int[] arr = {1,2,3,4,5,6,7};
int[] arr1 = Arrays.copyOf(arr, arr.length);
heapSort(arr);
Arrays.sort(arr1);
Assert.assertArrayEquals(arr, arr1);
}
}
五、復(fù)雜度。
時間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
