堆排序的整個流程可以切成兩段:先把資料整理成「堆」,再反覆把堆頂的最大值搬到尾端。
堆在本質上是一棵完全二元樹,但用陣列表示即可,不必真的建立節點。它必須滿足堆序性質:任一非葉節點的值都不小於(大根堆)或不於(小根堆)其左右子節點。
以索引 i 表示某節點時,其左子節點為 2i + 1、右子節點為 2i + 2。升序排序用大根堆,降序排序則用小根堆。建堆的做法是從「最後一個擁有子節點的節點」開始,一路往前對每個節點執行下沉調整,把最大值換到該子樹的根。
堆建立完成後,堆頂就是全域最大值。把它和陣列尾端交換,最大值就固定在尾端且不再參與後續調整;接著對剩下的 0 … i-1 區間重新下沉調整,讓新的最大值浮到堆頂。以此類推,尾端會依序填入第 2 大、第 3 大……直到排序完成。
// 下沉調整:讓 pos 位置的元素沿著較大的子節點往下換,直到符合大根堆
function headAdjust(elements, pos, len) {
var current = elements[pos];
var child = pos * 2 + 1; // 左子節點
while (child < len) {
// 若右子節點存在且更大,改與右子節點比較
if (child + 1 < len && elements[child] < elements[child + 1]) {
child += 1;
}
// 父節點已不小於最大的子節點,堆序恢復,收工
if (current >= elements[child]) break;
elements[pos] = elements[child]; // 子節點上移
pos = child;
child = pos * 2 + 1;
}
elements[pos] = current; // 原值放到最終落點
}
// 建堆:從最後一個有子節點的節點往前掃
function buildHeap(elements) {
for (var i = Math.floor(elements.length / 2) - 1; i >= 0; i--) {
headAdjust(elements, i, elements.length);
}
}
function sort(elements) {
buildHeap(elements);
for (var i = elements.length - 1; i > 0; i--) {
var swap = elements[i]; // 堆頂(最大值)換到尾端
elements[i] = elements[0];
elements[0] = swap;
headAdjust(elements, 0, i); // 對縮短後的區間重新調整
}
return elements;
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' + elements);
sort(elements);
console.log('after : ' + elements);
相比原始寫法,這裡把建堆的起點改成 Math.floor(length / 2) - 1(第一個非葉節點),並把下沉過程簡化為「記住原值、一路把子節點上提、最後一次寫入」,比較次數明顯下降,也更不容易寫錯。