[數(shù)據(jù)結(jié)構(gòu)] 堆與堆排序

本文介紹了堆這種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，以及堆排序算法，最后介紹了堆的相關(guān)應(yīng)用場景。

這篇文章使用 JavaScript 語言進行相關(guān)代碼的編寫。

數(shù)據(jù)結(jié)構(gòu)——堆 heap

基本概念與性質(zhì)

堆是一顆完全二叉樹，根據(jù)父子節(jié)點之間值的大小關(guān)系可以分為：

大根堆：每一個節(jié)點的值 大于或等于 其子節(jié)點的值；
小根堆：每一個節(jié)點的值 小于或等于 其子節(jié)點的值；

堆數(shù)據(jù)結(jié)構(gòu)的底層通常使用順序表進行存儲。

通過索引的計算可以快速得到子節(jié)點、父節(jié)點的值：

以 0 作為根節(jié)點的索引：（下文使用這種標準）

Parent(i) = (i-1)/2;
LeftChild(i) = i*2+1;
RightChild(i) = i*2+2;

以 1 作為根節(jié)點的索引：

Parent(i) = i/2;
LeftChild(i) = i*2;
RightChild(i) = i*2+1;

操作

一開始堆是一個空數(shù)組，最主要的兩個API是插入和刪除，這兩個操作會在堆的頭部和尾部進行操作，而這些操作會導(dǎo)致堆的性質(zhì)丟失，因此每次進行插入和刪除操作之后都需要重新維護堆的結(jié)構(gòu)。

插入

插入操作將一個新的數(shù)據(jù)添加到堆的末尾，然后向上調(diào)整。

圖片來源：二叉堆 - OI Wiki (oi-wiki.org)

刪除

刪除操作將根節(jié)點摘除，然后將堆的末尾的節(jié)點移動到堆的頂部，最后向下調(diào)整。

向上調(diào)整

對于某個節(jié)點（由一個明確的索引i指定），通過計算得到它的父節(jié)點的值，進行比較：

如果二者大小不滿足堆性質(zhì)，則交換（即上升），上升后繼續(xù)與新的父節(jié)點進行比較；
如果二者大小滿足堆性質(zhì)，則終止。

時間復(fù)雜度與樹的高度有關(guān)，這是完全二叉樹，即O(log N)

function up(index){
  while(true){
    const parent = (index-1)>>1;
    if(this.arr[parent] < this.arr[index]){
      [this.arr[index], this.arr[parent]] = [this.arr[parent], this.arr[index]];
      index = parent;
    }else{
      break;
    }
  }
}

(index-1)>>1是通過位運算快速實現(xiàn)向下取整的除以2，有時候懶得寫Math.floor...

向下調(diào)整

對于某個節(jié)點，通過索引計算得到左右兩個子節(jié)點，分別進行比較：（以小根堆為例）

如果當(dāng)前節(jié)點的值均小于左右兩個子節(jié)點的值，則說明滿足堆結(jié)構(gòu)，終止；
如果左右兩個子節(jié)點存在小于當(dāng)前節(jié)點的值，那么找出最小值，最小的節(jié)點與當(dāng)前節(jié)點進行交換（即下沉），下沉后繼續(xù)與新的左右子節(jié)點進行比較。

時間復(fù)雜度：O(log N)

function down(index){
  while(true){
    let left = index*2+1;
    let right = index*2+2;
    let target = index;
    if(left<this.size() && this.arr[left]>this.arr[index]){
      target = left;
    }
    if(right<this.size() && this.arr[right]>this.arr[index]){
      target = right;
      if(left<this.size() && this.arr[left]>this.arr[right]){
        target = left;
      }
    }
    if(target!==index){
      [this.arr[index], this.arr[target]] = [this.arr[target], this.arr[index]];
      index = target;
    }else{
      break;
    }
  }
}

完整代碼

class Heap {
  constructor(arr) {
    if(arr){
      this.arr = arr;
      for(let i=Math.floor((arr.length-1)/2); i>=0; i--){
        this._down(i);
      }
    }else{
      this.arr = [];
    }
  }

  size() {
    return this.arr.length;
  }

  push(val) {
    // 新的數(shù)據(jù)插入到尾部，然后向上調(diào)整
    this.arr.push(val);
    this._up(this.size() - 1);
  }

  top() {
    return this.arr[0];
  }

  pop() {
    // 沒有數(shù)據(jù)了，返回null
    if (this.size() == 0) return null;
    // 只剩下一個數(shù)據(jù)了，直接彈出返回
    if(this.size() == 1)return this.arr.pop();
    // 先記錄堆頂數(shù)據(jù)
    let top = this.top();
    // 將最后一個數(shù)據(jù)放到堆頂，然后向下調(diào)整
    let last = this.arr.pop();
    this.arr[0] = last;
    this._down(0);
    return top;
  }

  _up(index){
    while(true){
      const parent = (index-1)>>1;
      if(this.arr[parent] < this.arr[index]){
        [this.arr[index], this.arr[parent]] = [this.arr[parent], this.arr[index]];
        index = parent;
      }else{
        break;
      }
    }
  }

  _down(index){
    while(true){
      let left = index*2+1;
      let right = index*2+2;
      let target = index;
      if(left<this.size() && this.arr[left]>this.arr[index]){
        target = left;
      }
      if(right<this.size() && this.arr[right]>this.arr[index]){
        target = right;
        if(left<this.size() && this.arr[left]>this.arr[right]){
          target = left;
        }
      }
      if(target!==index){
        [this.arr[index], this.arr[target]] = [this.arr[target], this.arr[index]];
        index = target;
      }else{
        break;
      }
    }
  }
}

堆排序

堆排序是建立在堆這種數(shù)據(jù)結(jié)構(gòu)上的選擇排序。

首先建立大根堆，每次從根節(jié)點獲取最大值，將最大值移動到堆的尾部，然后對剩下的前n-1個節(jié)點進行維護大根堆的操作。

即：每次選擇最大值移動至尾部，再繼續(xù)在剩下的數(shù)中繼續(xù)查找最大值。

普通的選擇排序是在線性表上尋找最大值，時間復(fù)雜度為 \(O(n)\) ，要查找 \(n\) 個最大值，因此時間復(fù)雜度為 \(O(n^2)\).
在大根堆上尋找最大值的時間復(fù)雜度是\(O(1)\)，而獲取刪除最大值之后的向下調(diào)整操作時間復(fù)雜度為\(O(\log n)\)，共尋找 \(n\) 個最大值，因此時間復(fù)雜度為 \(O(n\log n)\)。

考慮到排序算法的輸入是一個亂序的數(shù)組，我們首要的任務(wù)是將一個普通的數(shù)組轉(zhuǎn)換成一個大根堆。

方法：從 最后一個節(jié)點的父節(jié)點 ，逆序遍歷數(shù)組，依次向下調(diào)整。

原理：自底向上，先保證子樹滿足堆性質(zhì)，然后逐漸向上擴展直到整棵樹都滿足堆性質(zhì)。

綜上，堆排序總共分為兩個步驟：

構(gòu)造大根堆
選擇排序 + 維護堆結(jié)構(gòu)

代碼

function heapSort(arr){
  const n = arr.length;
  // 從最后一個節(jié)點的父節(jié)點開始調(diào)整
  // 作用：構(gòu)造大根堆
  for(let i=Math.floor(n/2)-1; i>=0; i--){
    heapify(arr, i, n);
  } 
  // 將大根堆的根節(jié)點和最后一個節(jié)點交換，同時維護堆的性質(zhì)
  // 作用：排序
  for(let i=n-1; i>0; i--){
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, 0, i);
  }
}

// 調(diào)整堆
function heapify(arr, index, n){
  let left = 2*index+1;
  let right = 2*index+2;
  while(true){
    let largest = index;
    // 找到左右子樹中的最大值
    if(left<n && arr[left]>arr[largest]){
      largest = left;
    }
    if(right<n && arr[right]>arr[largest]){
      largest = right;
    }
    // 如果最大值不是根節(jié)點，則交換
    if(largest!==index){
      [arr[index], arr[largest]] = [arr[largest], arr[index]];
      // 更新下一輪的索引
      index = largest;
      left = 2*index+1;
      right = 2*index+2;
    }else{
      break;
    }
  }
}

堆的其它應(yīng)用

優(yōu)先隊列

優(yōu)先隊列是一種特殊的隊列，每個元素都有一個優(yōu)先級，按優(yōu)先級順序出隊。刷算法題的時候經(jīng)常會用到的輔助類PriorityQueue；

數(shù)組中的第 k 大（或小）元素

可以使用最小堆來高效找到第 \(k\) 大的元素。首先將前 \(k\) 個元素插入堆中，然后遍歷數(shù)組的其余部分，更新堆，保持堆的大小為 \(k\)。最終堆頂元素就是第 \(k\) 大的元素。

合并多個有序鏈表

使用最小堆來維護每個有序列表的當(dāng)前最小元素。每次從堆中取出最小元素，并將該元素所在列表的下一個元素插入堆中。重復(fù)該過程直到所有列表都被合并。

事件驅(qū)動模擬

在Node.js中，多個計時器回調(diào)就是使用最小堆記錄的，每次事件循環(huán)進行到timer階段，就檢查堆頂計時器的剩余時間是否已到達：

如果未到達，則執(zhí)行下一個階段的回調(diào)任務(wù)；
如果已到達，則執(zhí)行本階段的所有已到達的定時器回調(diào)任務(wù)；
- 每個回調(diào)執(zhí)行完成之后，如果是setInterval，則重新將任務(wù)添加到堆中。

posted @ 2024-07-28 00:55 feixianxing 閱讀(50) 評論(0) 收藏舉報

刷新頁面返回頂部

feixianxing