成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

如何用 JS 實現二叉堆

作者：北淵
開發 前端
二叉樹(Binary Tree)是一種樹形結構，它的特點是每個節點最多只有兩個分支節點，一棵二叉樹通常由根節點、分支節點、葉子節點組成，如下圖所示。每個分支節點也常常被稱作為一棵子樹，而二叉堆是一種特殊的樹，它屬于完全二叉樹。

[[384564]]

前言

二叉樹(Binary Tree)是一種樹形結構，它的特點是每個節點最多只有兩個分支節點，一棵二叉樹通常由根節點、分支節點、葉子節點組成，如下圖所示。每個分支節點也常常被稱作為一棵子樹，而二叉堆是一種特殊的樹，它屬于完全二叉樹。

二叉樹與二叉堆的關系

在日常工作中會遇到很多數組的操作，比如排序等。那么理解二叉堆的實現對以后的開發效率會有所提升，下面就簡單介紹一下什么是二叉樹，什么是二叉堆。

二叉樹特征

  • 根節點：二叉樹最頂層的節點
  • 分支節點：除了根節點以外且擁有葉子節點
  • 葉子節點：除了自身，沒有其他子節點

在二叉樹中，我們常常還會用父節點和子節點來描述，比如上圖中左側節點 2 為 6 和 3 的父節點，反之 6 和 3 是 2 子節點。

二叉樹分類

二叉樹分為滿二叉樹(full binary tree)和完全二叉樹(complete binary tree)。

  • 滿二叉樹：一棵深度為 k 且有 2 ^ k - 1個節點的二叉樹稱為滿二叉樹
  • 完全二叉樹：完全二叉樹是指最后一層左邊是滿的，右邊可能滿也可能不滿，然后其余層都是滿的二叉樹稱為完全二叉樹(滿二叉樹也是一種完全二叉樹)

二叉樹結構

從圖中我們可以看出二叉樹是從上到下依次排列下來，可想而知可以用一個數組來表示二叉樹的結構，從下標 index( 0 - 8 ) 從上到下依次排列。

 

  • 二叉樹左側節點表達式 index * 2 + 1。例如：以根節點為例求左側節點，根節點的下標為0，則左側節點的序數是1 ，對應數組中的值為1
  • 二叉樹右側節點表達式 index * 2 + 2。例如：以根節點為例求右側節點，根節點的下標為0，則右側節點的序數是2 ，對應數組中的值為 8
  • 二叉樹葉子節點表達式 序數 >= floor( N / 2 )都是葉子節點(N是數組的長度)。例如：floor( 9 / 2 ) = 4 ，則從下標 4 開始的值都為葉子節點

二叉堆特征

二叉堆是一個完全二叉樹，父節點與子節點要保持固定的序關系，并且每個節點的左子樹和右子樹都是一個二叉堆。

從上圖可以看出

  • 圖一：每個父節點大于子節點或等于子節點，滿足二叉堆的性質
  • 圖二：其中有一個父節點小于子節點則不滿足二叉堆性質

二叉堆分類

​ 二叉堆根據排序不同，可以分為最大堆和最小堆

  • 最大堆：根節點的鍵值是所有堆節點鍵值中最大者，且每個父節點的值都比子節點的值大
  • 最小堆：根節點的鍵值是所有堆節點鍵值中最小者，且每個父節點的值都比子節點的值小

如何實現二叉堆

通過上面的講述想必大家對二叉堆有了一定的理解，那么接下來就是如何實現。以最大堆為例，首先要初始化數組然后通過交換位置形成最大堆。

初始化二叉堆

從上面描述，我們可以知道二叉堆其實就是一個數組，那么初始化就非常簡單了。

 

  1. class Heap{ 
  2.   constructor(arr){ 
  3.     this.data = [...arr]; 
  4.     this.size = this.data.length; 
  5.   } 
  6. } 

父子節點交換位置

圖一中 2 作為父節點小于子節點，很顯然不符合最大堆性質。maxHeapify 函數可以把每個不符合最大堆性質的節點調換位置，從而滿足最大堆性質的數組。

調整步驟：

  • 調整分支節點 2 的位置(不滿足最大堆性質)
  • 獲取父節點 2 的左右節點 ( 12 , 5 ) ，從 ( 2 , 15 , 5 ) 中進行比較
  • 找出最大的節點與父節點進行交換，如果該節點本身為最大節點則停止操作
  • 重復 step2 的操作，從 2 , 4 , 7 中找出最大值與 2 做交換(遞歸)

 

  1. maxHeapify(i) { 
  2.   let max = i; 
  3.  
  4.   if(i >= this.size){ 
  5.     return; 
  6.   } 
  7.   // 當前序號的左節點 
  8.   const l = i * 2 + 1; 
  9.   // 當前需要的右節點 
  10.   const r = i * 2 + 2; 
  11.  
  12.   // 求當前節點與其左右節點三者中的最大值 
  13.   if(l < this.size && this.data[l] > this.data[max]){ 
  14.     max = l; 
  15.   } 
  16.   if(r < this.size && this.data[r] > this.data[max]){ 
  17.     max = r; 
  18.   } 
  19.  
  20.   // 最終max節點是其本身,則已經滿足最大堆性質，停止操作 
  21.   if(max === i) { 
  22.     return; 
  23.   } 
  24.  
  25.   // 父節點與最大值節點做交換 
  26.   const t = this.data[i]; 
  27.   this.data[i] = this.data[max]; 
  28.   this.data[max] = t; 
  29.  
  30.   // 遞歸向下繼續執行 
  31.   return this.maxHeapify(max); 
  32. } 

形成最大堆

我們可以看到，初始化是由一個數組組成，以下圖為例很顯然并不會滿足最大堆的性質，上述 maxHeapify 函數只是對某一個節點作出對調，無法對整個數組進行重構，所以我們要依次對數組進行遞歸重構。

  • 找到所有分支節點 Math.floor( N / 2 )(不包括葉子節點)
  • 將找到的子節點進行 maxHeapify 操作

 

  1. rebuildHeap(){ 
  2.   // 葉子節點 
  3.   const L = Math.floor(this.size / 2); 
  4.   for(let i = L - 1; i >= 0; i--){ 
  5.     this.maxHeapify(i); 
  6.   } 
  7. } 

生成一個升序的數組

  • swap 函數交換首位位置
  • 將最后一個從堆中拿出相當于 size - 1
  • 執行 maxHeapify 函數進行根節點比較找出最大值進行交換
  • 最終 data 會變成一個升序的數組

 

  1. sort() { 
  2.   for(let i = this.size - 1; i > 0; i--){ 
  3.     swap(this.data, 0, i); 
  4.     this.size--; 
  5.     this.maxHeapify(0); 
  6.   } 
  7. } 

插入方法

Insert 函數作為插入節點函數，首先

  1. 往 data 結尾插入節點
  2. 因為節點追加，size + 1
  3. 因為一個父節點擁有 2 個子節點，我們可以根據這個性質通過 isHeap 函數獲取第一個葉子節點，可以通過第一個葉子節點獲取新插入的節點，然后進行 3 個值的對比，找出最大值，判斷插入的節點。如果跟父節點相同則不進行重構(相等滿足二叉堆性質)，否則進行 rebuildHeap 重構堆

 

  1. isHeap() { 
  2.   const L = Math.floor(this.size / 2); 
  3.   for (let i = L - 1; i >= 0; i--) { 
  4.     const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER; 
  5.     const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER; 
  6.  
  7.     const max = Math.max(this.data[i], l, r); 
  8.  
  9.     if (max !== this.data[i]) { 
  10.       return false; 
  11.     } 
  12.     return true; 
  13.   } 
  14. } 
  15. insert(key) { 
  16.   this.data[this.size] = key; 
  17.   this.size++ 
  18.   if (this.isHeap()) { 
  19.     return; 
  20.   } 
  21.   this.rebuildHeap(); 
  22. } 

刪除方法

delete 函數作為刪除節點，首先

  • 刪除傳入index的節點
  • 因為節點刪除，size - 1
  • 重復上面插入節點的操作

 

  1. delete(index) { 
  2.   if (index >= this.size) { 
  3.     return; 
  4.   } 
  5.   this.data.splice(index, 1); 
  6.   this.size--; 
  7.   if (this.isHeap()) { 
  8.     return; 
  9.   } 
  10.   this.rebuildHeap(); 
  11. } 

完整代碼

 

  1. /** 
  2.  * 最大堆 
  3.  */ 
  4.  
  5. function left(i) { 
  6.   return (i * 2) + 1; 
  7. } 
  8.  
  9. function right(i) { 
  10.   return (i * 2) + 2; 
  11. } 
  12.  
  13. function swap(A, i, j) { 
  14.   const t = A[i]; 
  15.   A[i] = A[j]; 
  16.   A[j] = t; 
  17. } 
  18.  
  19. class Heap { 
  20.   constructor(arr) { 
  21.     this.data = [...arr]; 
  22.     this.size = this.data.length; 
  23.     this.rebuildHeap = this.rebuildHeap.bind(this); 
  24.     this.isHeap = this.isHeap.bind(this); 
  25.     this.sort = this.sort.bind(this); 
  26.     this.insert = this.insert.bind(this); 
  27.     this.delete = this.delete.bind(this); 
  28.     this.maxHeapify = this.maxHeapify.bind(this); 
  29.   } 
  30.  
  31.   /** 
  32.    * 重構堆，形成最大堆 
  33.    */ 
  34.   rebuildHeap() { 
  35.     const L = Math.floor(this.size / 2); 
  36.     for (let i = L - 1; i >= 0; i--) { 
  37.       this.maxHeapify(i); 
  38.     } 
  39.   } 
  40.  
  41.   isHeap() { 
  42.     const L = Math.floor(this.size / 2); 
  43.     for (let i = L - 1; i >= 0; i--) { 
  44.       const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER; 
  45.       const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER; 
  46.  
  47.       const max = Math.max(this.data[i], l, r); 
  48.  
  49.       if (max !== this.data[i]) { 
  50.         return false; 
  51.       } 
  52.       return true; 
  53.     } 
  54.   } 
  55.  
  56.   sort() { 
  57.     for (let i = this.size - 1; i > 0; i--) { 
  58.       swap(this.data, 0, i); 
  59.       this.size--; 
  60.       this.maxHeapify(0); 
  61.     } 
  62.   } 
  63.  
  64.   insert(key) { 
  65.     this.data[this.size++] = key; 
  66.     if (this.isHeap()) { 
  67.       return; 
  68.     } 
  69.     this.rebuildHeap(); 
  70.   } 
  71.  
  72.   delete(index) { 
  73.     if (index >= this.size) { 
  74.       return; 
  75.     } 
  76.     this.data.splice(index, 1); 
  77.     this.size--; 
  78.     if (this.isHeap()) { 
  79.       return; 
  80.     } 
  81.     this.rebuildHeap(); 
  82.   } 
  83.  
  84.   /** 
  85.    * 交換父子節點位置，符合最大堆特征 
  86.    * @param {*} i 
  87.    */ 
  88.   maxHeapify(i) { 
  89.     let max = i; 
  90.  
  91.     if (i >= this.size) { 
  92.       return; 
  93.     } 
  94.  
  95.     // 求左右節點中較大的序號 
  96.     const l = left(i); 
  97.     const r = right(i); 
  98.     if (l < this.size && this.data[l] > this.data[max]) { 
  99.       max = l; 
  100.     } 
  101.  
  102.     if (r < this.size && this.data[r] > this.data[max]) { 
  103.       max = r; 
  104.     } 
  105.  
  106.     // 如果當前節點最大，已經是最大堆 
  107.     if (max === i) { 
  108.       return; 
  109.     } 
  110.  
  111.     swap(this.data, i, max); 
  112.  
  113.     // 遞歸向下繼續執行 
  114.     return this.maxHeapify(max); 
  115.   } 
  116. } 
  117.  
  118. module.exports = Heap; 

示例

相信通過上面的講述大家對最大堆的實現已經有了一定的理解，我們可以利用這個來進行排序。

 

  1. const arr = [15, 12, 8, 2, 5, 2, 3, 4, 7]; 
  2. const fun = new Heap(arr); 
  3. fun.rebuildHeap(); // 形成最大堆的結構 
  4. fun.sort();// 通過排序，生成一個升序的數組 
  5. console.log(fun.data) // [2, 2, 3, 4, 5, 7, 8, 12, 15] 

總結

文章中主要講述了二叉樹、二叉堆的概念，然后通過代碼實現二叉堆。我們可以通過二叉堆來做排序和優先級隊列等。

責任編輯：未麗燕 來源： ZooTeam Blog
二叉樹二叉堆節點
相關推薦

2020-11-23 08:53:34

堆Heap

2020-08-31 07:43:58

二叉堆大頂堆存儲

2021-05-06 05:29:32

二叉堆數據結構算法

2023-04-06 07:39:48

2020-10-11 16:56:48

二叉搜索樹代碼開發

2020-04-27 07:05:58

二叉樹左子樹右子樹

2021-04-20 08:37:14

數據結構二叉樹樹

2023-07-31 08:01:13

二叉搜索測試

2021-09-03 08:58:00

二叉搜索樹節點

2009-08-11 13:29:57

C#二叉樹遍歷

2020-12-22 08:56:51

JavaScript數據結構前端

2022-10-12 23:25:17

二叉樹父節點根節點

2021-09-29 10:19:00

算法平衡二叉樹

2022-12-26 00:51:33

雙向鏈表二叉搜索樹

2020-12-11 09:49:29

二叉樹搜索樹數據

2009-05-27 09:38:32

C#二叉樹樹

2024-01-23 12:54:00

C++編程語言代碼

2021-04-28 20:12:27

數據結構創建

2013-07-15 16:35:55

二叉樹迭代器

2021-05-09 20:22:41

順序查找二叉查找數據結構
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板： 欧美国产视频一区二区 | 亚洲国产精品suv | 国产精品色哟哟网站 | 亚洲最新网址 | 日韩中文字幕 | 国产精品久久久久久久久污网站 | 在线观看亚洲 | 男人的天堂在线视频 | 女人牲交视频一级毛片 | 成人在线观看免费视频 | 免费同性女女aaa免费网站 | 黄色骚片| 亚洲国产中文字幕 | 国产精品视频网 | av在线黄| 亚洲二区视频 | 精品国产乱码久久久久久蜜退臀 | h视频在线免费看 | 国产激情在线播放 | 黄色一级免费 | 欧美区日韩区 | 一级片在线视频 | 国产欧美日韩综合精品一区二区 | 围产精品久久久久久久 | 日韩a| 亚洲欧美中文日韩在线v日本 | 欧美极品视频在线观看 | 日本免费视频在线观看 | www.操.com | 亚洲精品www久久久久久广东 | 亚洲成av人片在线观看无码 | 日韩成人在线观看 | 巨大荫蒂视频欧美另类大 | 亚洲精品一区二三区不卡 | 97精品视频在线 | 日韩欧美在线观看 | 成av在线| 亚洲一区二区在线播放 | 成人在线一区二区三区 | 久久久久精 | 免费在线观看黄视频 |