日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
面試官：說說你對堆的理解？如何實(shí)現(xiàn)？應(yīng)用場景？

本文轉(zhuǎn)載自微信公眾號「JS每日一題」，作者灰灰。轉(zhuǎn)載本文請聯(lián)系JS每日一題公眾號。

一、是什么

堆(Heap)是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱

堆通常是一個可以被看做一棵完全二叉樹的數(shù)組對象，如下圖：

總是滿足下列性質(zhì)：

  • 堆中某個結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
  • 堆總是一棵完全二叉樹

堆又可以分成最大堆和最小堆：

  • 最大堆：每個根結(jié)點(diǎn)，都有根結(jié)點(diǎn)的值大于兩個孩子結(jié)點(diǎn)的值
  • 最小堆：每個根結(jié)點(diǎn)，都有根結(jié)點(diǎn)的值小于孩子結(jié)點(diǎn)的值

二、操作

堆的元素存儲方式，按照完全二叉樹的順序存儲方式存儲在一個一維數(shù)組中，如下圖：

用一維數(shù)組存儲則如下：

 
 
 
 
    
  
  
  
  
  1. [0, 1, 2, 3, 4, 5, 6, 7, 8] 
    2.

根據(jù)完全二叉樹的特性，可以得到如下特性：

  • 數(shù)組零坐標(biāo)代碼的是堆頂元素
  • 一個節(jié)點(diǎn)的父親節(jié)點(diǎn)的坐標(biāo)等于其坐標(biāo)除以2整數(shù)部分
  • 一個節(jié)點(diǎn)的左節(jié)點(diǎn)等于其本身節(jié)點(diǎn)坐標(biāo) * 2 + 1
  • 一個節(jié)點(diǎn)的右節(jié)點(diǎn)等于其本身節(jié)點(diǎn)坐標(biāo) * 2 + 2

根據(jù)上述堆的特性，下面構(gòu)建最小堆的構(gòu)造函數(shù)和對應(yīng)的屬性方法：

 
 
 
 
    
  
  
  
  
  1. class MinHeap { 
    2. 
  
  
  
  
  2.   constructor() { 
    3. 
  
  
  
  
  3.     // 存儲堆元素 
    4. 
  
  
  
  
  4.     this.heap = [] 
    5. 
  
  
  
  
  5.   } 
    6. 
  
  
  
  
  6.   // 獲取父元素坐標(biāo) 
    7. 
  
  
  
  
  7.   getParentIndex(i) { 
    8. 
  
  
  
  
  8.     return (i - 1) >> 1 
    9. 
  
  
  
  
  9.   } 
    10. 
  
  
  
  
  10.    
    11. 
  
  
  
  
  11.   // 獲取左節(jié)點(diǎn)元素坐標(biāo) 
    12. 
  
  
  
  
  12.   getLeftIndex(i) { 
    13. 
  
  
  
  
  13.     return i * 2 + 1 
    14. 
  
  
  
  
  14.   } 
    15. 
  
  
  
  
  15.    
    16. 
  
  
  
  
  16.  // 獲取右節(jié)點(diǎn)元素坐標(biāo) 
    17. 
  
  
  
  
  17.   getRightIndex(i) { 
    18. 
  
  
  
  
  18.     return i * 2 + 2 
    19. 
  
  
  
  
  19.   } 
    20. 
  
  
  
  
  20.    
    21. 
  
  
  
  
  21.   // 交換元素 
    22. 
  
  
  
  
  22.   swap(i1, i2) { 
    23. 
  
  
  
  
  23.     const temp = this.heap[i1] 
    24. 
  
  
  
  
  24.     this.heap[i1] = this.heap[i2] 
    25. 
  
  
  
  
  25.     this.heap[i2] = temp 
    26. 
  
  
  
  
  26.   } 
    27. 
  
  
  
  
  27.    
    28. 
  
  
  
  
  28.   // 查看堆頂元素 
    29. 
  
  
  
  
  29.   peek() { 
    30. 
  
  
  
  
  30.     return this.heap[0] 
    31. 
  
  
  
  
  31.   } 
    32. 
  
  
  
  
  32.    
    33. 
  
  
  
  
  33.   // 獲取堆元素的大小 
    34. 
  
  
  
  
  34.   size() { 
    35. 
  
  
  
  
  35.     return this.heap.length 
    36. 
  
  
  
  
  36.   } 
    37. 
  
  
  
  
  37. } 
    38.

涉及到堆的操作有：

  • 插入
  • 刪除

插入

將值插入堆的底部，即數(shù)組的尾部，當(dāng)插入一個新的元素之后，堆的結(jié)構(gòu)就會被破壞，因此需要堆中一個元素做上移操作

將這個值和它父節(jié)點(diǎn)進(jìn)行交換，直到父節(jié)點(diǎn)小于等于這個插入的值，大小為k的堆中插入元素的時間復(fù)雜度為O(logk)

如下圖所示，22節(jié)點(diǎn)是新插入的元素，然后進(jìn)行上移操作：

相關(guān)代碼如下：

 
 
 
 
    
  
  
  
  
  1. // 插入元素 
    2. 
  
  
  
  
  2. insert(value) { 
    3. 
  
  
  
  
  3.   this.heap.push(value) 
    4. 
  
  
  
  
  4.   this.shifUp(this.heap.length - 1) 
    5. 
  
  
  
  
  5. } 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. // 上移操作 
    8. 
  
  
  
  
  8. shiftUp(index) { 
    9. 
  
  
  
  
  9.   if (index === 0) { return } 
    10. 
  
  
  
  
  10.   const parentIndex = this.getParentIndex(index) 
    11. 
  
  
  
  
  11.   if(this.heap[parentIndex] > this.heap[index]){ 
    12. 
  
  
  
  
  12.     this.swap(parentIndex, index) 
    13. 
  
  
  
  
  13.     this.shiftUp(parentIndex) 
    14. 
  
  
  
  
  14.   } 
    15. 
  
  
  
  
  15. } 
    16.

刪除

常見操作是用數(shù)組尾部元素替換堆頂，這里不直接刪除堆頂，因?yàn)樗械脑貢蚯耙苿右晃?，會破壞了堆的結(jié)構(gòu)

然后進(jìn)行下移操作，將新的堆頂和它的子節(jié)點(diǎn)進(jìn)行交換，直到子節(jié)點(diǎn)大于等于這個新的堆頂，刪除堆頂?shù)臅r間復(fù)雜度為O(logk)

整體如下圖操作：

相關(guān)代碼如下：

 
 
 
 
    
  
  
  
  
  1. // 刪除元素 
    2. 
  
  
  
  
  2. pop() { 
    3. 
  
  
  
  
  3.   this.heap[0] = this.heap.pop() 
    4. 
  
  
  
  
  4.   this.shiftDown(0) 
    5. 
  
  
  
  
  5. } 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. // 下移操作 
    8. 
  
  
  
  
  8. shiftDown(index) { 
    9. 
  
  
  
  
  9.   const leftIndex = this.getLeftIndex(index) 
    10. 
  
  
  
  
  10.   const rightIndex = this.getRightIndex(index) 
    11. 
  
  
  
  
  11.   if (this.heap[leftIndex] < this.heap[index]){ 
    12. 
  
  
  
  
  12.     this.swap(leftIndex, index) 
    13. 
  
  
  
  
  13.     this.shiftDown(leftIndex) 
    14. 
  
  
  
  
  14.   } 
    15. 
  
  
  
  
  15.   if (this.heap[rightIndex] < this.heap[index]){ 
    16. 
  
  
  
  
  16.     this.swap(rightIndex, index) 
    17. 
  
  
  
  
  17.     this.shiftDown(rightIndex) 
    18. 
  
  
  
  
  18.   } 
    19. 
  
  
  
  
  19. } 
    20.

時間復(fù)雜度

關(guān)于堆的插入和刪除時間復(fù)雜度都是Olog(n)，原因在于包含n個節(jié)點(diǎn)的完全二叉樹，樹的高度不會超過log2n

堆化的過程是順著節(jié)點(diǎn)所在路徑比較交換的，所以堆化的時間復(fù)雜度跟樹的高度成正比，也就是Olog(n)，插入數(shù)據(jù)和刪除堆頂元素的主要邏輯就是堆化

三、總結(jié)

堆是一個完全二叉樹

堆中每一個節(jié)點(diǎn)的值都必須大于等于(或小于等于)其子樹中每個節(jié)點(diǎn)的值

對于每個節(jié)點(diǎn)的值都大于等于子樹中每個節(jié)點(diǎn)值的堆，叫作“大頂堆”

對于每個節(jié)點(diǎn)的值都小于等于子樹中每個節(jié)點(diǎn)值的堆，叫作“小頂堆”

根據(jù)堆的特性，我們可以使用堆來進(jìn)行排序操作，也可以使用其來求第幾大或者第幾小的值

參考文獻(xiàn)

https://baike.baidu.com/item/%E5%A0%86/20606834

https://xlbpowder.cn/2021/02/26/%E5%A0%86%E5%92%8C%E5%A0%86%E6%8E%92%E5%BA%8F/


本文題目：面試官：說說你對堆的理解？如何實(shí)現(xiàn)？應(yīng)用場景？
URL分享：http://www.5511xx.com/article/cocppcg.html