JS實現堆排序

Scorpion 發布于2019-08-22 18:31 / 1833人閱讀

摘要：堆的存儲堆由數組來實現，相當于對二叉樹做層序遍歷。實現交換兩個節點將結點以下的堆整理為大頂堆，注意這一步實現的基礎實際上是假設結點以下的子堆已經是一個大頂堆，函數實現的功能是實際上是找到結點在包括結點的堆中的正確位置。

堆的預備知識

堆是一個完全二叉樹。

完全二叉樹：二叉樹除開最后一層，其他層結點數都達到最大，最后一層的所有結點都集中在左邊（左邊結點排列滿的情況下，右邊才能缺失結點）。

大頂堆：根結點為最大值，每個結點的值大于或等于其孩子結點的值。

小頂堆：根結點為最小值，每個結點的值小于或等于其孩子結點的值。

堆的存儲：堆由數組來實現，相當于對二叉樹做層序遍歷。如下圖：

對于結點 i ，其子結點為 2i+1 與 2i+2 。

堆排序算法

現在需要對如上二叉樹做升序排序，總共分為三步：

將初始二叉樹轉化為大頂堆（heapify）（實質是從第一個非葉子結點開始，從下至上，從右至左，對每一個非葉子結點做shiftDown操作），此時根結點為最大值，將其與最后一個結點交換。

除開最后一個結點，將其余節點組成的新堆轉化為大頂堆（實質上是對根節點做shiftDown操作），此時根結點為次最大值，將其與最后一個結點交換。

重復步驟2，直到堆中元素個數為1（或其對應數組的長度為1），排序完成。

下面詳細圖解這個過程：

步驟1：

初始化大頂堆，首先選取最后一個非葉子結點(我們只需要調整父節點和孩子節點之間的大小關系，葉子結點之間的大小關系無需調整)。設數組為arr，則第一個非葉子結點的下標為：i = Math.floor(arr.length/2 - 1) = 1，也就是數字4，如圖中虛線框，找到三個數字的最大值，與父節點交換。

然后，下標 i 依次減1（即從第一個非葉子結點開始，從右至左，從下至上遍歷所有非葉子節點）。后面的每一次調整都是如此：找到父子結點中的最大值，做交換。

這一步中數字6、1交換后，數字[1,5,4]組成的堆順序不對，需要執行一步調整。因此需要注意，每一次對一個非葉子結點做調整后，都要觀察是否會影響子堆順序！

這次調整后，根節點為最大值，形成了一個大頂堆，將根節點與最后一個結點交換。

步驟2：

除開當前最后一個結點6(即最大值)，將其余結點[4,5,3,1]組成新堆轉化為大頂堆(注意觀察，此時根節點以外的其他結點，都滿足大頂堆的特征，所以可以從根節點4開始調整，即找到4應該處于的位置即可)。

步驟3：

接下來反復執行步驟2，直到堆中元素個數為1：

堆中元素個數為1，排序完成。

JavaScript實現

// 交換兩個節點
function swap(A, i, j) {
  let temp = A[i];
  A[i] = A[j];
  A[j] = temp; 
}

// 將 i 結點以下的堆整理為大頂堆，注意這一步實現的基礎實際上是：
// 假設 結點 i 以下的子堆已經是一個大頂堆，shiftDown函數實現的
// 功能是實際上是：找到 結點 i 在包括結點 i 的堆中的正確位置。后面
// 將寫一個 for 循環，從第一個非葉子結點開始，對每一個非葉子結點
// 都執行 shiftDown操作，所以就滿足了結點 i 以下的子堆已經是一大
//頂堆
function shiftDown(A, i, length) {
  let temp = A[i]; // 當前父節點
// j=0; i--) {
    shiftDown(A, i, A.length);
  }
  // 排序，每一次for循環找出一個當前最大值，數組長度減一
  for(let i = Math.floor(A.length-1); i>0; i--) {
    swap(A, 0, i); // 根節點與最后一個節點交換
    shiftDown(A, 0, i); // 從根節點開始調整，并且最后一個結點已經為當
                         // 前最大值，不需要再參與比較，所以第三個參數
                         // 為 i，即比較到最后一個結點前一個即可
  }
}

let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
heapSort(Arr);
alert(Arr);

程序注釋：將 i 結點以下的堆整理為大頂堆，注意這一步實現的基礎實際上是：假設結點 i 以下的子堆已經是一個大頂堆，shiftDown函數實現的功能是實際上是：找到結點 i 在包括結點 i 的堆中的正確位置。后面做第一次堆化時，heapSort 中寫了一個 for 循環，從第一個非葉子結點開始，對每一個非葉子結點都執行 shiftDown操作，所以就滿足了每一次 shiftDown中，結點 i 以下的子堆已經是一大頂堆。

復雜度分析：adjustHeap 函數中相當于堆的每一層只遍歷一個結點，因為
具有n個結點的完全二叉樹的深度為[log2n]+1，所以 shiftDown的復雜度為 O(logn)，而外層循環共有 f(n) 次，所以最終的復雜度為 O(nlogn)。

堆的應用

堆主要是用來實現優先隊列，下面是優先隊列的應用示例：

操作系統動態選擇優先級最高的任務執行。

靜態問題中，在N個元素中選出前M名，使用排序的復雜度：O(NlogN)，使用優先隊列的復雜度: O(NlogM)。

而實現優先隊列采用普通數組、順序數組和堆的不同復雜度如下：

使用堆來實現優先隊列，可以使入隊和出隊的復雜度都很低。

云服務器 GPU云服務器堆排序堆排序算法堆排序排序c語言 js實現table排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/95953.html

JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0
排序算法速度測試（插入排序、二分法插入、選擇排序、快速排序、堆排序）js實現

摘要：公共函數庫用于取出隨機排列的數字原數組給原數組賦值排序算法插入排序時間復雜度二分法插入排序選擇排序快速排序一堆排序測試用例插入排序時間測試二分法插入排序時間測試選擇排序時間測試快速排序時間測試一堆公共函數庫（用于取出隨機排列的數字） module.exports={ randomIntegerArray:function(count){ var origina...

mochixuan 2019-08-20 16:04 評論0 收藏0
堆排序 js實現

摘要：堆排序實現最近在看語言版的數據結構，用法著實很難，于是按照意思，仿照語言寫了版的三種排序方法僅供大家一起學習和參考后續比較難的歸并排序，和快速排序，以后再說，廢話不說，直接邊代碼邊講解希爾排序，將表分為幾段長度，分別進行排序，然后進行總的排堆排序 js實現 /* 最近在看c語言版的數據結構，c用法著實很難，于是按照意思，仿照c語言寫了javascript版的三種排序方法！僅供大家一...

elva 2019-08-20 16:05 評論0 收藏0
js實現堆排序

摘要：堆排序構造大頂堆第一個元素就是最大的，然后跟最后一個元素交換，把最大的彈出棧第一個元素與它的左右子節點比較，左右子節點中較大的比它大則交換然后再遞歸地這樣交換下去直到沒有比它大的子節點或者沒有子節點。堆排序構造大頂堆第一個元素就是最大的，然后跟最后一個元素交換，把最大的彈出棧第一個元素與它的左右子節點比較，左右子節點中較大的比它大則交換然后再遞歸地這樣交換下去直到沒有比它大的子節...

big_cat 2019-08-20 15:16 評論0 收藏0
基于 Javascript 排序算法

摘要：適用于數據比較少或基本有序的情況。插入排序時間復雜度為，空間復雜度為，屬于穩定排序。算法適用于少量數據的排序。就像下圖這樣，可以理解桶的意思下圖是整個排序過程示意圖基數排序時間復雜度為，空間復雜度為，屬于穩定排序。寫在前面個人感覺：javascript對類似排序查找這樣的功能已經有了很好的封裝，以致于當我們想對數組排序的時候只需要調用arr.sort()方法，而查找數組元素也只需要...

tommego 2019-08-23 11:47 評論0 收藏0