建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號(hào)「JS每日一題」，作者灰灰。轉(zhuǎn)載本文請(qǐng)聯(lián)系JS每日一題公眾號(hào)。
一、是什么
堆(Heap)是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱
堆通常是一個(gè)可以被看做一棵完全二叉樹的數(shù)組對(duì)象，如下圖：
總是滿足下列性質(zhì)：
- 堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值
- 堆總是一棵完全二叉樹
堆又可以分成最大堆和最小堆：
- 最大堆：每個(gè)根結(jié)點(diǎn)，都有根結(jié)點(diǎn)的值大于兩個(gè)孩子結(jié)點(diǎn)的值
- 最小堆：每個(gè)根結(jié)點(diǎn)，都有根結(jié)點(diǎn)的值小于孩子結(jié)點(diǎn)的值
二、操作
堆的元素存儲(chǔ)方式，按照完全二叉樹的順序存儲(chǔ)方式存儲(chǔ)在一個(gè)一維數(shù)組中，如下圖：
用一維數(shù)組存儲(chǔ)則如下：
- [0, 1, 2, 3, 4, 5, 6, 7, 8]
根據(jù)完全二叉樹的特性，可以得到如下特性：
- 數(shù)組零坐標(biāo)代碼的是堆頂元素
- 一個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)的坐標(biāo)等于其坐標(biāo)除以2整數(shù)部分
- 一個(gè)節(jié)點(diǎn)的左節(jié)點(diǎn)等于其本身節(jié)點(diǎn)坐標(biāo) * 2 + 1
- 一個(gè)節(jié)點(diǎn)的右節(jié)點(diǎn)等于其本身節(jié)點(diǎn)坐標(biāo) * 2 + 2
根據(jù)上述堆的特性，下面構(gòu)建最小堆的構(gòu)造函數(shù)和對(duì)應(yīng)的屬性方法：
- class MinHeap {
- constructor() {
- // 存儲(chǔ)堆元素
- this.heap = []
- }
- // 獲取父元素坐標(biāo)
- getParentIndex(i) {
- return (i - 1) >> 1
- }
- // 獲取左節(jié)點(diǎn)元素坐標(biāo)
- getLeftIndex(i) {
- return i * 2 + 1
- }
- // 獲取右節(jié)點(diǎn)元素坐標(biāo)
- getRightIndex(i) {
- return i * 2 + 2
- }
- // 交換元素
- swap(i1, i2) {
- const temp = this.heap[i1]
- this.heap[i1] = this.heap[i2]
- this.heap[i2] = temp
- }
- // 查看堆頂元素
- peek() {
- return this.heap[0]
- }
- // 獲取堆元素的大小
- size() {
- return this.heap.length
- }
- }
涉及到堆的操作有：
- 插入
- 刪除
插入
將值插入堆的底部，即數(shù)組的尾部，當(dāng)插入一個(gè)新的元素之后，堆的結(jié)構(gòu)就會(huì)被破壞，因此需要堆中一個(gè)元素做上移操作
將這個(gè)值和它父節(jié)點(diǎn)進(jìn)行交換，直到父節(jié)點(diǎn)小于等于這個(gè)插入的值，大小為k的堆中插入元素的時(shí)間復(fù)雜度為O(logk)
如下圖所示，22節(jié)點(diǎn)是新插入的元素，然后進(jìn)行上移操作：
相關(guān)代碼如下：
- // 插入元素
- insert(value) {
- this.heap.push(value)
- this.shifUp(this.heap.length - 1)
- }
- // 上移操作
- shiftUp(index) {
- if (index === 0) { return }
- const parentIndex = this.getParentIndex(index)
- if(this.heap[parentIndex] > this.heap[index]){
- this.swap(parentIndex, index)
- this.shiftUp(parentIndex)
- }
- }
刪除
常見操作是用數(shù)組尾部元素替換堆頂，這里不直接刪除堆頂，因?yàn)樗械脑貢?huì)向前移動(dòng)一位，會(huì)破壞了堆的結(jié)構(gòu)
然后進(jìn)行下移操作，將新的堆頂和它的子節(jié)點(diǎn)進(jìn)行交換，直到子節(jié)點(diǎn)大于等于這個(gè)新的堆頂，刪除堆頂?shù)臅r(shí)間復(fù)雜度為O(logk)
整體如下圖操作：
相關(guān)代碼如下：
- // 刪除元素
- pop() {
- this.heap[0] = this.heap.pop()
- this.shiftDown(0)
- }
- // 下移操作
- shiftDown(index) {
- const leftIndex = this.getLeftIndex(index)
- const rightIndex = this.getRightIndex(index)
- if (this.heap[leftIndex] < this.heap[index]){
- this.swap(leftIndex, index)
- this.shiftDown(leftIndex)
- }
- if (this.heap[rightIndex] < this.heap[index]){
- this.swap(rightIndex, index)
- this.shiftDown(rightIndex)
- }
- }
時(shí)間復(fù)雜度
關(guān)于堆的插入和刪除時(shí)間復(fù)雜度都是Olog(n)，原因在于包含n個(gè)節(jié)點(diǎn)的完全二叉樹，樹的高度不會(huì)超過(guò)log2n
堆化的過(guò)程是順著節(jié)點(diǎn)所在路徑比較交換的，所以堆化的時(shí)間復(fù)雜度跟樹的高度成正比，也就是Olog(n)，插入數(shù)據(jù)和刪除堆頂元素的主要邏輯就是堆化
三、總結(jié)
堆是一個(gè)完全二叉樹
堆中每一個(gè)節(jié)點(diǎn)的值都必須大于等于(或小于等于)其子樹中每個(gè)節(jié)點(diǎn)的值
對(duì)于每個(gè)節(jié)點(diǎn)的值都大于等于子樹中每個(gè)節(jié)點(diǎn)值的堆，叫作“大頂堆”
對(duì)于每個(gè)節(jié)點(diǎn)的值都小于等于子樹中每個(gè)節(jié)點(diǎn)值的堆，叫作“小頂堆”
根據(jù)堆的特性，我們可以使用堆來(lái)進(jìn)行排序操作，也可以使用其來(lái)求第幾大或者第幾小的值
參考文獻(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/
分享名稱：面試官：說(shuō)說(shuō)你對(duì)堆的理解？如何實(shí)現(xiàn)？應(yīng)用場(chǎng)景？
地址分享：http://m.fisionsoft.com.cn/article/cocppcg.html
