JS實(shí)現(xiàn)堆排序

Scorpion 發(fā)布于2019-08-22 18:31 / 1841人閱讀

摘要：堆的存儲(chǔ)堆由數(shù)組來實(shí)現(xiàn)，相當(dāng)于對(duì)二叉樹做層序遍歷。實(shí)現(xiàn)交換兩個(gè)節(jié)點(diǎn)將結(jié)點(diǎn)以下的堆整理為大頂堆，注意這一步實(shí)現(xiàn)的基礎(chǔ)實(shí)際上是假設(shè)結(jié)點(diǎn)以下的子堆已經(jīng)是一個(gè)大頂堆，函數(shù)實(shí)現(xiàn)的功能是實(shí)際上是找到結(jié)點(diǎn)在包括結(jié)點(diǎn)的堆中的正確位置。

堆的預(yù)備知識(shí)

堆是一個(gè)完全二叉樹。

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

大頂堆：根結(jié)點(diǎn)為最大值，每個(gè)結(jié)點(diǎn)的值大于或等于其孩子結(jié)點(diǎn)的值。

小頂堆：根結(jié)點(diǎn)為最小值，每個(gè)結(jié)點(diǎn)的值小于或等于其孩子結(jié)點(diǎn)的值。

堆的存儲(chǔ)：堆由數(shù)組來實(shí)現(xiàn)，相當(dāng)于對(duì)二叉樹做層序遍歷。如下圖：

對(duì)于結(jié)點(diǎn) i ，其子結(jié)點(diǎn)為 2i+1 與 2i+2 。

堆排序算法

現(xiàn)在需要對(duì)如上二叉樹做升序排序，總共分為三步：

將初始二叉樹轉(zhuǎn)化為大頂堆（heapify）（實(shí)質(zhì)是從第一個(gè)非葉子結(jié)點(diǎn)開始，從下至上，從右至左，對(duì)每一個(gè)非葉子結(jié)點(diǎn)做shiftDown操作），此時(shí)根結(jié)點(diǎn)為最大值，將其與最后一個(gè)結(jié)點(diǎn)交換。

除開最后一個(gè)結(jié)點(diǎn)，將其余節(jié)點(diǎn)組成的新堆轉(zhuǎn)化為大頂堆（實(shí)質(zhì)上是對(duì)根節(jié)點(diǎn)做shiftDown操作），此時(shí)根結(jié)點(diǎn)為次最大值，將其與最后一個(gè)結(jié)點(diǎn)交換。

重復(fù)步驟2，直到堆中元素個(gè)數(shù)為1（或其對(duì)應(yīng)數(shù)組的長(zhǎng)度為1），排序完成。

下面詳細(xì)圖解這個(gè)過程：

步驟1：

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

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

這一步中數(shù)字6、1交換后，數(shù)字[1,5,4]組成的堆順序不對(duì)，需要執(zhí)行一步調(diào)整。因此需要注意，每一次對(duì)一個(gè)非葉子結(jié)點(diǎn)做調(diào)整后，都要觀察是否會(huì)影響子堆順序！

這次調(diào)整后，根節(jié)點(diǎn)為最大值，形成了一個(gè)大頂堆，將根節(jié)點(diǎn)與最后一個(gè)結(jié)點(diǎn)交換。

步驟2：

除開當(dāng)前最后一個(gè)結(jié)點(diǎn)6(即最大值)，將其余結(jié)點(diǎn)[4,5,3,1]組成新堆轉(zhuǎn)化為大頂堆(注意觀察，此時(shí)根節(jié)點(diǎn)以外的其他結(jié)點(diǎn)，都滿足大頂堆的特征，所以可以從根節(jié)點(diǎn)4開始調(diào)整，即找到4應(yīng)該處于的位置即可)。

步驟3：

接下來反復(fù)執(zhí)行步驟2，直到堆中元素個(gè)數(shù)為1：

堆中元素個(gè)數(shù)為1，排序完成。

JavaScript實(shí)現(xiàn)

// 交換兩個(gè)節(jié)點(diǎn)
function swap(A, i, j) {
  let temp = A[i];
  A[i] = A[j];
  A[j] = temp; 
}

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

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

程序注釋：將 i 結(jié)點(diǎn)以下的堆整理為大頂堆，注意這一步實(shí)現(xiàn)的基礎(chǔ)實(shí)際上是：假設(shè) 結(jié)點(diǎn) i 以下的子堆已經(jīng)是一個(gè)大頂堆，shiftDown函數(shù)實(shí)現(xiàn)的功能是實(shí)際上是：找到結(jié)點(diǎn) i 在包括結(jié)點(diǎn) i 的堆中的正確位置。后面做第一次堆化時(shí)，heapSort 中寫了一個(gè) for 循環(huán)，從第一個(gè)非葉子結(jié)點(diǎn)開始，對(duì)每一個(gè)非葉子結(jié)點(diǎn)都執(zhí)行 shiftDown操作，所以就滿足了每一次 shiftDown中，結(jié)點(diǎn) i 以下的子堆已經(jīng)是一大頂堆。

復(fù)雜度分析：adjustHeap 函數(shù)中相當(dāng)于堆的每一層只遍歷一個(gè)結(jié)點(diǎn)，因?yàn)?br>具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1，所以 shiftDown的復(fù)雜度為 O(logn)，而外層循環(huán)共有 f(n) 次，所以最終的復(fù)雜度為 O(nlogn)。

堆的應(yīng)用

堆主要是用來實(shí)現(xiàn)優(yōu)先隊(duì)列，下面是優(yōu)先隊(duì)列的應(yīng)用示例：

操作系統(tǒng)動(dòng)態(tài)選擇優(yōu)先級(jí)最高的任務(wù)執(zhí)行。

靜態(tài)問題中，在N個(gè)元素中選出前M名，使用排序的復(fù)雜度：O(NlogN)，使用優(yōu)先隊(duì)列的復(fù)雜度: O(NlogM)。

而實(shí)現(xiàn)優(yōu)先隊(duì)列采用普通數(shù)組、順序數(shù)組和堆的不同復(fù)雜度如下：

使用堆來實(shí)現(xiàn)優(yōu)先隊(duì)列，可以使入隊(duì)和出隊(duì)的復(fù)雜度都很低。

云服務(wù)器 GPU云服務(wù)器堆排序堆排序算法堆排序排序c語言 js實(shí)現(xiàn)table排序

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/95953.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Scorpion

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

Java學(xué)習(xí)路線總結(jié)，搬磚工逆襲Java架構(gòu)師（全網(wǎng)最強(qiáng)）

閱讀 1529·2021-11-18 10:02
2021年8月國(guó)產(chǎn)數(shù)據(jù)庫(kù)大事記

閱讀 1681·2021-09-04 16:40
RAKsmart：八月美國(guó)服務(wù)器$30/月起,圣何塞/洛杉磯/日本/韓國(guó)等;新增香港大帶寬高防服務(wù)器

閱讀 3180·2021-09-01 10:48
webpack4 單獨(dú)抽離打包 css 的新實(shí)現(xiàn)

閱讀 882·2019-08-30 15:55
Grid布局——頁(yè)面布局如此簡(jiǎn)單

閱讀 1860·2019-08-30 15:55
如何利用css3設(shè)置獨(dú)特背景

閱讀 1379·2019-08-30 13:05
ios9.3為前端帶來哪些新特性

閱讀 3022·2019-08-30 12:52
Css優(yōu)先級(jí)

閱讀 1632·2019-08-30 11:24

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

JS實(shí)現(xiàn)堆排序

相關(guān)文章

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

排序算法速度測(cè)試（插入排序、二分法插入、選擇排序、快速排序、堆排序）js實(shí)現(xiàn)

堆排序 js實(shí)現(xiàn)