引言

在我們前面的文章中，我們探討了以「分治法」為基礎的排序演算法，例如快速排序和合併排序，並展示了它們如何在前端特效應用中進行視覺化處理。然而，除了分治法，另一個經典且高效的排序演算法是「堆排序」（Heap Sort），它基於完全二元樹的特性來進行排序操作。

今天，我們將介紹堆排序的基本概念，並通過程式碼逐步展示其視覺化實作。這篇文章將重點放在演算法步驟的動畫化處理，讓你看到如何在前端動畫系統中以直觀方式呈現堆排序。

線上查看動畫效果

二元樹結構

我們先來介紹資料結構，這個結構的好處是，可以利用陣列來儲存節點，並且透過一個簡單的索引規則找到每個父節點的子節點。並限定每個節點最多擁有兩個子節點，所有層的節點都是從左至右排列緊密的。

索引規則

• 每個節點 𝑖 的左子節點的索引值為：2 × 𝑖 + 1
• 每個節點 𝑖 的右子節點的索引值為：2 × 𝑖 + 2

假設我們有一個包含 7 個節點的完全二元樹，可以將其用陣列表示為：
[黃0,紅1,紅2,藍3,藍4,藍5,藍6]

其中三個顏色分別代表不同階層

1. 根節點（黃0）是陣列中的第 0 個元素，它的兩個子節點是：
   • 紅1：2 × 0 + 1 = 1
   • 紅2：2 × 0 + 2 = 2
2. 節點（紅1）是第 1 個元素，它的兩個子節點是：
   • 藍3：2 × 1 + 1 = 3
   • 藍4：2 × 1 + 2 = 4
3. 節點（紅2）是第 2 個元素，它的兩個子節點是：
   • 藍5：2 × 2 + 1 = 5
   • 藍6：2 × 2 + 2 = 6

堆排序

堆排序的核心概念是通過建立最大堆來將數列進行排序。在最大堆中，每個父節點的值都大於或等於其子節點的值。接著，我們通過反覆將最大堆的堆頂元素移到陣列末端，並對剩餘的部分重新調整堆，來完成排序過程。

function heapSort(arr) {
    const n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
    return arr;
}

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

這個方法的聰明之處在於，建立好最大堆後，我們僅僅把最大值和末尾進行交換，此時我們只需要找到下一個最大值，並通過層層交換把它擺上最上層，就再一次完成最大堆的排序了。

迭代方程式

為了實現動畫效果，我們將堆排序的過程分為三個階段：建堆、交換、和排序。在這裡，利用和前幾次相同的狀態管理架構，並透過不同的階段來逐步呈現視覺化動畫效果。這樣的設計可以讓每個排序步驟清晰可見，並允許我們控制動畫的進度。

class SortAlgorithm{
    heapSortSetting(columns){
        this.i = Math.floor(columns.length / 2) - 1;
        this.j = this.i;
        this.heapPhase = "1.build";
    }
    heapSort(columns){
        const len = columns.length;
        const i = this.i;
        const j = this.j;
        switch(this.heapPhase){
            case "1.build":
            case "2.swap":
            case "3.sort":
        }
    }
}

階段１：建堆

在建堆階段，我們將從數列的中間偏左開始，向左逐步對每個節點進行 heapify，將其轉換為最大堆。如果所有節點都已處理完，我們會進入下一階段，開始交換。

case "1.build":
    this.j = SortAlgorithm.heapify(columns, len, j);
    if(this.j == -1){
        this.i--;
        this.j = this.i;
        if(this.i < 0){
            this.i = len - 1;
            this.j = 0;
            this.heapPhase = "2.swap";
        }
    }
    break;

選在中間相當於從二元樹的最底層開始，當它儲存在陣列中，表示最後一組父子關係的索引值是[中間, 中間 * 2 +1, 中間 * 2 + 2]

階段２：交換

在交換階段，我們將堆頂的最大元素與陣列末端的元素交換，這樣最大值就被移到了陣列的正確位置。

case "2.swap":
    const a = columns[0];
    const b = columns[i];
    SortAlgorithm.swapColumn(a, b, 60);
    this.heapPhase = "3.sort";
    break;

階段３：排序

最後，我們對剩餘的部分再次進行 heapify，並重複上一步驟，直到所有元素都已排序完成。

case "3.sort":
    this.j = SortAlgorithm.heapify(columns, i, j);
    if(this.j == -1){
        this.j = 0;
        this.i--;
        this.heapPhase = "2.swap";
        if(this.i < 0) return true;
    }
    break;

Heapify 函式實作

建堆的方式和範例程式碼相同，要注意的地方在於，在不能使用遞迴的前提下，我們利用回傳值來進行下一次的 heapify，以此達到迭代的效果。

class SortAlgorithm{
    static heapify(columns, len, i){
        let largest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < len && columns[left].height > columns[largest].height) {
            largest = left;
        }
        if (right < len && columns[right].height > columns[largest].height) {
            largest = right;
        }
        if (largest !== i) {
            const a = columns[i];
            const b = columns[largest];
            SortAlgorithm.swapColumn(a, b, 60);
            return largest;
        }
        return -1;
    }
}

這邊可以特別強調的是，二元樹的空間大小是 2^n - 1，我們的資料有可能小於這個空間，因此，在 heapify 的時候會先檢查子節點是否存在，是否超出陣列範圍

迭代器和生成器

接下來讓我們介紹如何使用生成器（Generators）來實作 堆排序（Heap Sort） 的迭代版本，簡直是不費吹灰之力，就從範例程式碼改成我們所需的視覺化版本了！

主要階段

生成器在 JavaScript 中是一種特殊的函數，允許函數的執行被暫停和恢復，並可以在每次呼叫 yield 時返回當前狀態。在這裡負責執行兩個主要階段：建堆、排序

class SortAlgorithmIterable{
    * heapSortMaker(columns) {
        const n = columns.length;
        for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
            yield* this.heapify(columns, n, i);
        }
        for (let i = n - 1; i > 0; i--) {
            const a = columns[0];
            const b = columns[i];
            SortAlgorithm.swapColumn(a, b, 60);
            yield* this.heapify(columns, i, 0);
        }
        yield true;
    }
}

Heapify

和前面邏輯相同，在這裡我們不需要通過回傳值來手動迭代，可以透過 yield* 來呼叫遞迴函式。

class SortAlgorithmIterable{
    * heapify(columns, n, i) {
        yield false;
        let largest = i;
        let left = 2 * i + 1;
        let right = 2 * i + 2;
        if (left < n && columns[left].height > columns[largest].height) largest = left;
        if (right < n && columns[right].height > columns[largest].height) largest = right;
        if (largest !== i) {
            const a = columns[largest];
            const b = columns[i];
            SortAlgorithm.swapColumn(a, b, 60);
            yield* this.heapify(columns, n, largest);
        }
    }
}

結論

堆排序的程式碼雖然簡潔，空間概念相對來說比其他排序演算法要稍微複雜一些，因為它涉及到樹狀結構的調整和多階段的操作。儘管如此，我們仍然可以通過合理的狀態機設計，將每個步驟逐一展現，並保持排序的可視化和動畫效果。

而基於生成器的堆排序不僅能夠保留原本演算法的結構，還可以清晰地觀察每個排序步驟，讓我們對演算法的內部運作有了更具體的理解。隨著生成器的應用，動畫化的遞迴流程變得更加輕鬆和高效，展示了生成器在處理複雜邏輯的靈活性。