堆排序(英語：Heapsort)是指利用堆這種資料結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于(或者大于)它的父節點。
我們将給定的數組想象成一個完全二叉樹，那麼數組元素與二叉樹節點的對應關系如下：
可以看到 0 的子元素為 1 、 2 ， 1 的子元素為 3 ， 4 、 3 的子元素為 7 、 8。
及對應關系為：下标為 n 的元素的左子元素下标為 2n+1 , 右子元素下标為 2n+2 。根據該對應關系，我們可以将數組看作一個滿足堆積性質的完全二叉樹，借助二叉樹的性質來進行排序。
簡單來說：堆排序是将資料看成是完全二叉樹、根據完全二叉樹的特性來進行排序的一種算法。
按堆積性質，堆可以分為 最大堆 和 最小堆：最大堆要求節點的元素都要不小于其孩子，最小堆要求節點元素都不大于其左右孩子。那麼以最大堆為例，處于最大堆的根節點的元素一定是這個堆中的最大值。
下面僅讨論最大堆：
我們從最底層節點開始建構最大堆，依次向上。因為每個節點的兩棵子樹已經被我們建構為了最大堆，是以選擇兩個子樹的根節點及目前節點中的最大值即為以目前節點為根的樹中的最大值。
及自下向上建構最大堆時，我們在每一層隻需比較根元素及其兩個孩子節點即可正确的建構最大堆。我們對一個兩層的完全二叉樹的建堆代碼如下：
public static void sortNode(int[] nums, int head, intend) {if (head < 0) {throw new RuntimeException("堆頂超過左邊界");
}int length =nums.length;//左子節點坐标
int left = head * 2 + 1;//右子節點坐标
int right = left + 1;//判斷左子節點是否存在
if (left <=end) {//如果左子節點更大，交換
if (nums[left] >nums[head]) {int temp =nums[head];
nums[head]=nums[left];
nums[left]=temp;
}
}//判斷右子節點是否存在
if (right <=end) {//如果右子節點更大，交換
if (nums[right] >nums[head]) {int temp =nums[head];
nums[head]=nums[right];
nums[right]=temp;
}
}
}
基于對兩層完全二叉樹的建堆，我們可以将整個數組建構為一個最大堆：
public static void sortHeap(int[] nums, intend) {int length =nums.length;for (int i = (end - 1) / 2; i >= 0; i--) {
sortNode(nums, i, end);
}
}
但是需要注意的是，最大堆使得以二叉樹的角度了解數組，數組是符合堆積性質的，但數組并不是有序的。
以下面的最大堆為例：
可以看出，這是一個符合堆積性質的最大堆，但它并不是一個有序的數組，我們将其還原成數組：
這是因為，堆積性質隻規定了根元素與孩子節點之間的大小關系，至于左孩子與右孩子之間的大小關系是沒有限制的。也就是說，根節點一定大于兩個孩子節點，但兩個孩子節點間是無序的。
是以建構最大堆對于排序來說，意義是為我們找到了序列中的最大值，而不是讓整個數組變的有序。
我們可以通過不斷的通過建堆找出剩餘元素中的極值來完成排序。我們完整的排序操作如下：
1. 将整個數組建構為一個最大堆，此時 nums[0] 即是數組中的最大值。
2. 将 num[0] 與 nums[length-1] 互換。
3. 将 0到length-2 将的元素建構為最大堆，此時 nums[0] 即是數組中除第一步找出的最大值外的的最大值。
4. 将 num[0] 與 nums[length-2] 互換。
5. 重複上述操作，直到可以用來建構堆的元素僅剩 nums[0]， 整個數組排序完畢。
可以看到，我們對 n 個元素建堆一次，需要 log2n 次計算，而整個過程需要建堆 n 次，是以時間複雜度為O(nlog2n ) 。而我們在排序過程中采用了互換位置的就地排序方式，沒有使用額外的空間存儲數組，空間複雜度為O(1) 。因為我們進行了多次建堆，數值相同的元素被冒到堆頂的順序是不确定的，是以堆排序是不穩定排序。
基于上面展示的兩個方法，堆排序的實作為：
public static void heapSort(int[] nums) {if (nums == null) {throw new RuntimeException("數組為空");
}int length =nums.length;for (int i = length - 1; i >= 0; i--) {
sortHeap(nums, i);int temp = nums[0];
nums[0] =nums[i];
nums[i]=temp;
}
}