資料結構 - Heap - PHP 實作

# Introduction

最近在解 Leetcode Top K Frequent Elements 題目時, 會需要使用到 priority
queue, 而 priority queue 的實作便是使用 Heap, 因此就有了這一篇

# 概念

Heap 的概念大概如上圖, 主要規則如下：

• root 為 index 0 的位置
• parent 比 child 小的稱為 Min Heap, 而 parent 比 child 大的稱為 Max Heap, 比如上圖的 root 0 的值為 1, 小於 3 以及 6, 以此往下類推, index 1 值為 3 小於 5
  以及 9
• Heap 必須是一個 complete binary tree
• child 的 index 會剛好等於 parent index * 2 or parent index * 2 + 1, 比如上圖中的 index 0, 其 child 剛好等於 1, 2

# 實作 binary heap

# create & insert

• 先建立一個 class, 建立一個 array 代表 heap, 一個 count 代表目前 heap 內有多少 node, 這邊可以看到, 為什麼是 $size + 1 呢？ 因為我們要讓 heap 的 index 是從 1 開始的, 這樣才能使用 2n & 2n+1 來取得 left & right child

  <?php
  class MinHeap { 
  
      public $heap; 
      public $count; 
  
      public function __construct(int $size) { 
          $this->heap = array_fill(0, $size + 1, 0); 
          $this->count = 0; 
      } 
  }

• 接下來實作 create & insert, 簡單來說, 當我們新增一個 node 到 heap 中, 我們首先將它置於 heap 的最後一個 index, 然後我們開始拿它跟它的 parent 比較, 如果它小於它的 parent, 則把兩個位置互換, 重複這個動作, 直到該 node 被置於正確的位置 (符合上面介紹的 heap 的規則)

  <?php
  public function create(array $arr = []) { 
      if ($arr) { 
          foreach ($arr as $val) { 
              $this->insert($val); 
          } 
      } 
  } 
  
  public function insert(int $i) { 
      if ($this->count == 0) { 
          $this->heap[1] = $i; 
          $this->count = 2; 
      } 
      else { 
          $this->heap[$this->count++] = $i; 
          $this->siftUp(); 
      } 
  } 
  
  public function siftUp() { 
      $currentPos = $this->count - 1; 
      $parentPos = intval($currentPos / 2); 
  
      while ($currentPos > 0 &&  
      $this->heap[$parentPos] > $this->heap[$currentPos]) { 
          $this->swap($currentPos, $parentPos); 
          $currentPos = intval($parentPosPos / 2); 
          $parentPos = intval($currentPos / 2); 
      } 
  } 
  
  public function swap(int $a, int $b) { 
      $parentPos = $this->heap[$a]; 
      $this->heap[$a] = $this->heap[$b]; 
      $this->heap[$b] = $parentPos; 
  }

# 取出最小值:

• 取得 root index 的值, 並將原先排在 heap 最後 index 的值拉到第一個
• 然後依序檢查新的 root index 的值是否有小於兩個 children
• 把 root index 換成三個 node 裡面最小的值
• 然後回到與之交換的 child, 重複上面的步驟, 直到整個 heap 符合規則

  <?php
  public function extractMin() { 
      $min = $this->heap[1]; 
      $this->heap[1] = $this->heap[$this->count - 1]; 
      $this->heap[--$this->count] = 0; 
      $this->siftDown(1); 
      return $min; 
  }
  
  public function siftDown(int $k) { 
      $smallest = $k; 
      $left = 2 * $k; 
      $right = 2 * $k + 1; 
  
      if ($left < $this->count &&  
      $this->heap[$smallest] > $this->heap[$left]) { 
          $smallest = $left; 
      } 
  
      if ($right < $this->count && $this->heap[$smallest] > $this->heap[$right]) { 
          $smallest = $right; 
      }
  
      if ($smallest != $k) {
          $this->swap($k, $smallest); 
          $this->siftDown($smallest); 
      }
  } 

# binary heap 時間 & 空間複雜度

# Questions and Answers

以下的 image 是屬於哪一種資料結構？

• Example:
  
• Answer:
  max-heap

heap 資料結構中, 如果 root 小於 child nodes, 又稱為？

min-heap

heap 資料結構中, 如果 root 大於 child nodes, 又稱為？

max-heap