> 引用：[https://www.cnblogs.com/chengxiao/p/6129630.html](https://www.cnblogs.com/chengxiao/p/6129630.html)
堆的概念：
1. 堆就是一個棵二叉樹（每個節點 `最多有兩個子節點` 的結構）
2. 大頂堆：每個節點的值都比子節點的值大（所以，堆頂元素肯定是最大的）
3. 大頂堆：每個節點的值都比子節點的值小（所以，堆頂元素肯定是最小的）
堆可以保存在數組中，在數組中的特點：
第 i 個節點的 左子節點下標是 2i+1
右子節點下標是 2i+2
在數組中使用編號來表示：
堆排序的實現思路：
1. 先把數組構造成一個大頂堆
2. 把頂堆元素（最大）放到數組的最后
3. 把數組中除了最后一個元素（已經排好序的最大元素）之外的數組當成一個數組，重新構造成一個大頂堆
4. 再把堆頂（下標為0）元素（第2大）放到數組倒數第2 的位置以此類推 ....
# 實現
## 步驟一 構造初始堆。將給定無序序列構造成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)。
此時，我們就將一個無需序列構造成了一個大頂堆。
## 步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大。然后繼續調整et堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復進行交換、重建、交換。
# JavaScript
~~~
let len
function heapSort(arr) {
len = arr.length
// 1. 從最后一個“非葉子節點”（len/2-1)構造大頂堆
for(let i=Math.floor(len/2)-1;i>=0;i--) {
// 調整節點為大頂
heapify(arr, i)
}
// 2. 依次把根節點移動到數組最后，并重新調整大頂堆
for(let i=arr.length-1;i>0;i--) {
// 把第一個元素（最大的）交換到最后
[arr[0],arr[i]] = [arr[i],arr[0]]
// 長度減少（以后省略最后一個元素）
len--
// 從根節點開始重新調整為大頂堆
heapify(arr, 0)
}
}
function heapify(arr, i) {
let left = 2*i+1,
right = 2*i + 2,
largest = i // 默認節點為最大元素
// 如果有左子節點，并且左子節點大于父節點
if(left < len && arr[left] > arr[largest]) {
// 標記左子節點更大
largest=left
}
// 如果有右子節點，并且右子節點大于父節點
if(right < len && arr[right] > arr[largest]) {
// 標記右子節點更大
largest=right
}
// 如果標記最大的元素不是父節點
if(i!=largest) {
// 那么父節點和大的子節點交換
[arr[i],arr[largest]] = [arr[largest],arr[i]]
// 對交換之后的節點再次調整
heapify(arr, largest)
}
}
~~~
