JavaScript 中的堆排序

簡介

在本指南中，我們將探討堆排序 - 其背後的理論以及如何在 JavaScript 中實現堆排序。

我們將從它所基於的數據結構開始（這裡的大量預示：它是一個 堆 !)，如何對該數據結構執行操作，以及如何將該數據結構用作一種有效的排序算法。

數據結構和排序算法是編程中的核心概念。計算機程序始終處理大型數據集，令人作嘔地檢索和注入數據。我們組織這些數據集並對其進行操作的方式非常重要，因為它直接影響用戶與我們的應用程序交互的難易程度和速度。

排序算法基於兩個特徵進行評估：時間 和空間 該算法用作數據集大小的函數。這些被稱為時間複雜度 和空間複雜性 分別，並允許我們在平均和最佳情況下將算法相互“坑”。

堆排序被認為是一種高效的算法，平均時間複雜度為θ(n log(n)) .

儘管存在其他算法在平均情況下優於堆排序，但它的重要性取決於它在最壞情況下以與最佳情況下相同的效率執行的能力，使其在不同的數據集上具有穩定的運行時間，而一些算法可能會遭受大的或小的影響 - 取決於它們的潛在機制。

JavaScript 中的堆排序

它不需要輔助數據結構 - 它就地對數據進行排序 並影響原始數據（就地 ）。它不保留 相對順序 或相等的元素 .如果您在未排序的集合中有兩個具有相同值的元素，則它們的相對順序可能會在已排序的集合中更改（或保持不變）（不穩定 ）。最後，將元素相互比較以找到它們的順序（comparison-based )。

雖然 Heap Sort 是 in-place 的（不需要輔助數據結構），但是為了讓實現更清晰一些，我們會在排序的時候額外增加一個數組。

堆排序的底層機制相當簡單，有些人甚至稱其為“改進的選擇排序” .

它首先將未排序的數組轉換為堆 - 最大堆 或 最小堆 .在最大堆的情況下，每個父元素都比其後代擁有更大的值，從而使根元素成為堆中最大的元素，反之亦然。

堆排序依賴於這個堆條件 .

在每次迭代中，該算法刪除堆的根並將其推入一個空數組。每次刪除後，堆都會恢復自身，將其第二大（或第二小）元素冒泡到根以保持其堆狀態。這個過程也被稱為heapifying 你會經常看到人們將這樣做的方法稱為 heapify .

堆排序繼續將新定位的根元素移動到排序後的數組中，直到一個都沒有。

以這種方式使用最大堆將導致數組中的元素按降序排列。要使數組按升序排列，必須選擇最小堆。

這種自排序和選擇性刪除讓人想起選擇排序（沒有自排序部分），因此平行的人畫。

什麼是堆 ?

堆是一種樹狀數據結構。我們將用於我們的目的的堆類型將是二叉樹（一種類似於樹分支的數據結構，並且必須從一個節點開始，如果要分支出來，則最多允許從每個節點擴展兩個後繼）。雖然堆的類型很少，但堆有兩個顯著特徵：

1. 堆必須是完整的， 這意味著樹的每一層都應該從左到右填充，並且不允許在不填充最後一層剩餘的所有可能節點的情況下創建樹的另一層。

1. 每個節點必須保存一個大於或等於（在最小堆的情況下，小於或等於）其每個後代的值的值。這稱為“堆條件”。

將堆映射到數組

到目前為止，我們所定義和描繪的堆只是一個圖表，一個圓和線的集合。要在基於 JavaScript 的計算機程序中使用這種結構，我們需要將其重新加工成數組或列表。

幸運的是，這是一個相當簡單的操作，它首先模仿了我們構建堆的方式。我們按照將元素放入堆中的相同順序讀取堆中的元素並將其轉移到數組中：從左到右逐級。

在此轉變之後，堆及其對應數組的示例：

這樣，我們不僅可以設法在代碼中表達一個堆，而且我們還獲得了一個在該堆內導航的指南針。我們可以推導出三個方程，給定每個節點的索引，將指向它的父節點及其在數組中的左右子節點的位置：

在 JavaScript 中創建堆

現在堆的詳細定義已經到位，我們可以繼續將其實現為 JavaScript 類。

免費電子書：Git Essentials

查看我們的 Git 學習實踐指南，其中包含最佳實踐、行業認可的標準以及隨附的備忘單。停止谷歌搜索 Git 命令並真正學習 它！

在本指南中，我們將創建並使用一個最大堆。由於最大堆和最小堆之間的區別是微不足道的，並且不會影響堆排序算法背後的一般邏輯，因此最小堆的實現以及因此通過堆排序創建升序是一個問題更改比較運算符。

讓我們繼續定義一個 MaxHeap 類：

class MaxHeap{
    constructor(){
        this.heap = [];
    }

    parentIndex(index){
        return Math.floor((index-1)/2);
    }

    leftChildIndex(index){
        return (2*index + 1);
    }

    rightChildIndex(index){
        return (2*index + 2);
    }
}

在 MaxHeap 類，我們定義了一個初始化一個空數組的構造函數。稍後，我們將創建額外的函數來在這個數組中填充一個堆。

然而，目前我們只創建了幫助函數，它們將返回給定節點的父節點和子節點的索引。

向堆中插入元素

每當一個新元素被插入到堆中時，它就會被放置在底層最右邊的節點旁邊（數組表示中的最後一個空白空間），或者，如果底層已經滿，則放在新層的最左邊節點.在這個場景中，保證了堆的第一個要求：樹的完整性。

展望未來，需要重新建立可能受到干擾的堆屬性。要將新元素移動到堆上的適當位置，則將其與其父元素進行比較，如果新元素大於其父元素，則交換元素。

新元素在堆中冒泡，同時在每個級別與其父元素進行比較，直到最終恢復堆屬性：

讓我們將此功能添加到我們之前創建的 MaxHeap 類中：

 swap(a, b) {
        let temp = this.heap[a];
        this.heap[a] = this.heap[b];
        this.heap[b] = temp;
    }

 insert(item) {
    this.heap.push(item);
    var index = this.heap.length - 1;
    var parent = this.parentIndex(index);
    while(this.heap[parent] && this.heap[parent] < this.heap[index]) {
        this.swap(parent, index);
        index = this.parentIndex(index);
        parent = this.parentIndex(index);
    }
}

swap() 被添加為輔助方法，以節省代碼中的一些冗餘，因為在插入新元素時，我們可能必須多次執行此操作 - 一個介於零和 log(n) 之間的數字 （在新元素大於堆根的情況下，我們必須讓它爬上高度為 log(the-total-number-of-its-elements) - 換句話說，是一個 lot .

insert() 操作如下：

1. 將給定元素附加到 heap 使用內置 JavaScript 方法：push() .
2. 標記heap的最後一個元素 作為 index 及其父級為 parent .
3. 雖然在索引 parent 處存在堆元素 (this.heap[parent] )，並且該元素恰好小於 index 處的元素 (this.heap[parent] < this.heap[index ), insert() 方法繼續交換兩者（this.swap(parent, index) ) 並將光標向上移動一級。

從堆中移除元素

堆只允許刪除根元素，這之後給我們留下了一個完全扭曲的堆。為此，我們首先要恢復完全二叉樹 通過將堆的最後一個節點移動到根來獲得屬性。然後我們需要冒泡 這個放錯位置的值直到堆屬性恢復原位：

delete() {
    var item = this.heap.shift();
    this.heap.unshift(this.heap.pop());
    var index = 0;
    var leftChild = this.leftChildIndex(index);
    var rightChild = this.rightChildIndex(index);
    while(this.heap[leftChild] && this.heap[leftChild] > this.heap[index] || this.heap[rightChild] > this.heap[index]){
        var max = leftChild;
        if(this.heap[rightChild] && this.heap[rightChild] > this.heap[max]){
            max = rightChild
        }
        this.swap(max, index);
        index = max;
        leftChild = this.leftChildIndex(max);
        rightChild = this.rightChildIndex(max);
    }
    return item;
}

delete() 方法，我們在 MaxHeap 中創建 類，操作方式如下：

1. 該方法首先收集最大的元素 - 因此，堆的數組表示中的第一個元素。內置 shift() 方法刪除數組的第一個元素並返回刪除的元素，然後我們將其存儲在 item 變量。
2. heap的最後一個元素 通過 pop() 被移除 並被放置到最近清空的 heap 的第一個空間 通過 unshift() . unshift() 是一種內置的 JavaScript 方法，與 shift() 對應 .而 shift() 刪除數組的第一個元素並將其餘元素向後移動一個空格，unshift() 將一個元素推到數組的開頭，並將其餘元素向前移動一個空格。
3. 為了能夠使新根向下冒泡，指向它的位置（最初為 0）及其兩個子節點（index , rightChild , leftChild ) 被創建。
4. while() 循環檢查 index 是否存在左孩子 節點以確保下面的另一個級別的存在（尚未檢查右子節點）以及該級別中的任何子節點是否大於 [index 處的節點 ]。
5. 如果滿足while循環內的條件，則max 創建變量以聲明左節點是該方法遇到的最大值。然後在循環內，在 if 子句，我們檢查是否存在右孩子，如果存在，它是否比我們首先檢查的左孩子大。如果右孩子的值確實更大，它的索引替換max中的值 .
6. 通過 this.swap(max, index) 將持有較大值的子代與其父代交換 .
7. 該方法在 while 循環結束時將其假想光標下移一級，然後一遍又一遍地執行 while 循環內的代碼，直到其條件不再成立。

在 JavaScript 中實現堆排序

最後，為了實現本指南的承諾，我們創建了一個 heapSort() 函數（這次在 MaxHeap 之外 class)，並為它提供一個我們想要排序的數組：

function heapSort(arr){
    var sorted = [];
    var heap1 = new MaxHeap();
    
    for(let i=0; i<arr.length; i++){
        heap1.insert(arr[i]);
    }
    
    for(let i=0; i<arr.length; i++){
        sorted.push(heap1.delete());
    }
    return sorted;
}

heapSort() 將要排序的數組作為其參數。然後，它創建一個空數組來放置排序後的版本，以及一個用於執行排序的空堆。

然後，heap1 填充有 arr 的元素 並被一一刪除，將刪除的元素推入排序數組。 heap1 每次刪除都會自組織，因此只需將元素從其中推入排序數組即可使用排序數組。

讓我們創建一個數組並測試一下：

let arr = [1, 6, 2, 3, 7, 3, 4, 6, 9];
arr = heapSort(arr);

console.log(arr);

結論

在本指南中，我們了解了堆數據結構以及堆排序的操作方式。

堆排序雖然不是最快的算法，但在數據部分排序或需要穩定算法時可能會有優勢。

儘管我們使用額外的數據結構來實現它，但堆排序本質上是一種就地排序算法，因此，有時也可以在內存使用受到關注時使用。