上一節的堆排序，我們開辟了額外的空間進行構造堆和對堆進行排序。這一小節，我們進行優化，使用原地堆排序。
對于一個最大堆，首先将開始位置資料和數組末尾數值進行交換，那麼數組末尾就是最大元素，然後再對W元素進行 shift down 操作，重新生成最大堆，然後将新生成的最大數和整個數組倒數第二位置進行交換，此時到處第二位置就是倒數第二大資料，這個過程以此類推。
整個過程可以用如下圖表示：
源碼包下載下傳：Download
package runoob.heap;
import runoob.sort.SortTestHelper;
/**
* 原地堆排序
*/
public class HeapSort<T extends Comparable> {
public static void sort(Comparable[] arr) {
int n = arr.length;
// 注意，此時我們的堆是從0開始索引的
// 從(最後一個元素的索引-1)/2開始
// 最後一個元素的索引 = n-1
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
shiftDown(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
// 交換堆中索引為i和j的兩個元素
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
// 原始的shiftDown過程
private static void shiftDown(Comparable[] arr, int n, int k) {
while (2 * k + 1 < n) {
//左孩子節點
int j = 2 * k + 1;
//右孩子節點比左孩子節點大
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
j += 1;
//比兩孩子節點都大
if (arr[k].compareTo(arr[j]) >= 0) break;
//交換原節點和孩子節點的值
swap(arr, k, j);
k = j;
// 測試 HeapSort
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
// 将heapify中的資料逐漸使用extractMax取出來
// 取出來的順序應該是按照從大到小的順序取出來的
for (int i = 0; i < N; i++) {
System.out.print(arr[i] + " ");
// 確定arr數組是從大到小排列的
for (int i = 1; i < N; i++)
assert arr[i - 1] >= arr[i];
}