堆積樹(Heap Tree)

Da-Wei Chiang

大綱

  • 何謂堆積樹
  • 圖例堆積樹
    • 堆積樹的結構
    • 堆積樹的建構過程
      • Buttom Up
      • Top Down
    • 取根節點
    • 插入節點
  • 實作練習
  • Heap Tree的Big O

何謂堆積樹

  • 堆積樹也是一種二元樹, 每個節點下只有兩個子節點. 更具體的說, 堆積樹是一顆完全二元樹
  • 堆積樹有以下兩種形式
    • 最小堆積樹(Minimum Heap)
      • 根節點的值為整個樹的最小值, 且每個父節點的值需小於等於子節點的值.同層之間的值不比大小
    • 最大堆積樹(Maximum Heap)
      • 根節點的值為整個樹的最大值, 且每個父節點的值需大於等於子節點的值.同層之間的值不比大小

堆積樹的結構

堆積樹的建構過程

  • 堆積樹(Max/Min Heap)的建立有兩種形式
    • 由下而上(Buttom Up)
    • 由上而下(Top Down)

堆積樹的建構過程 - Buttom Up - Min Heap(Step 1)

  • 假定有一組數分別為15, 8, 20, 18, 17, 25, 19, 5要如何使用Buttom Up建構Min Heap？
  • Step 1:先依數組順序產生Binary Complete Tree

堆積樹的建構過程 - Buttom Up - Min Heap(Step 2)

  • Step 2:由下而上, 從有子節點的父節點開始逐一交換節點
    • 18具有子節點, 且5小於18故交換
    • 交換完後, 8具備子節點, 且子節點中5小於8故交換
    • 交換完後, 20具備子節點, 且子節點中19小於20故交換
    • 交換完後, 15具備子節點, 且子節點中5小於15故交換
    • 交換致Root後如下一頁投影片右下圖的Tree所示

堆積樹的建構過程 - Buttom Up - Min Heap(Step 2)

堆積樹的建構過程 - Buttom Up - Min Heap(Step 3)

  • 由於最後Root節點15是跟左子樹·5交換, 故檢查左子樹是否符合Min Heap規則
    • 父節點15與子節點8跟17中, 8小於15故交換
    • 交換完後, 15小於子節點18故維持不變, 完成Buttom Up - Min Heap, 如右下圖所示

堆積樹的建構過程 - Top Down - Min Heap

  • 假定有一組數分別為15, 8, 20, 18, 17, 25, 19, 5要如何使用Top Down建構Min Heap？
  • Top Down的建構方式
    • 每當新增一個節點時, 比較該節點與父節點是否符合Min Heap, 若不符合則交換

堆積樹的建構過程 - Top Down - Min Heap

  • 假定有一組數分別為15, 8, 20, 18, 17, 25, 19, 5

堆積樹的建構過程 - Top Down - Min Heap

  • 假定有一組數分別為15, 8, 20, 18, 17, 25, 19, 5

堆積樹的建構過程 - Top Down - Min Heap

  • 假定有一組數分別為15, 8, 20, 18, 17, 25, 19, 5

練習

  • 請使用紙筆, 對數組15, 8, 20, 18, 17, 25, 19, 5使用Buttom Up與Top Down建立Map Heap

動腦想想看

  • Buttom Up與Top Down使用同一組數所建構的Heap Tree一定會一樣嗎？

Heap Tree取值

  • Min Heap取根節點
    • Step 1: 取出根節點
    • Step 2: 將Binary Complete Tree中的最後一個節點移至根節點
    • Step 3: 開始由根節點看子節點, 將「比較小」的節點與根節點交換
  • Max Heap取根節點
    • Step 1: 取出根節點
    • Step 2: 將Binary Complete Tree中的最後一個節點移至根節點
    • Step 3: 開始由根節點看子節點, 將「比較大」的節點與根節點交換

圖例Min Heap取根節點

圖例Min Heap取根節點

圖例Min Heap取根節點

練習

  • 承上題
    • 請使用紙筆, 對數組15, 8, 20, 18, 17, 25, 19, 5使用Buttom Up與Top Down建立Map Heap
  • 對此Map Heap取根節點

動腦想想看

  • 如果今天取的並非根節點, 應該要怎麼做？

插入節點

  • 先將預插入節點新增於Binary Complete Tree中, 再一步一步逐一調整Tree

圖例插入節點

  • 對於一個Min Heap新增節點3

圖例插入節點

圖例插入節點

圖例插入節點

實作練習

  • python內建函數 - Min Heap

python內建函數 - Min Heap

import heapq

heapq.heapify(data_Set)  #Create MinHeapTree
heapq.heappush(data_Set, data)   #Insert data
heapq.heappop(data_Set)   #Pop Root
In [4]:
## 範例 - Create Min Heap
import heapq

data = [15, 8, 20, 18, 17, 25, 19, 5]
print('Original Data:', data)
heapq.heapify(data)
print('Min Heap Tree:', data)

Original Data: [15, 8, 20, 18, 17, 25, 19, 5]
Min Heap Tree: [5, 8, 19, 15, 17, 25, 20, 18]
In [1]:
## 範例 - Insert data to Min Heap
import heapq

data = [15, 8, 20, 18, 17, 25, 19, 5]
print('Original Data:', data)
heapq.heapify(data)
heapq.heappush(data, 3)
print('Min Heap Tree:', data)

Original Data: [15, 8, 20, 18, 17, 25, 19, 5]
Min Heap Tree: [3, 5, 19, 8, 17, 25, 20, 18, 15]
In [3]:
## 範例 - Insert data to Min Heap
import heapq

data = [15, 8, 20, 18, 17, 25, 19, 5]
print('Original Data:', data)
heapq.heapify(data)
print('Min Heap Tree:', data)
Root = heapq.heappop(data)
print('Root:', Root)
print('Min Heap Tree:', data)

Original Data: [15, 8, 20, 18, 17, 25, 19, 5]
Min Heap Tree: [5, 8, 19, 15, 17, 25, 20, 18]
Root: 5
Min Heap Tree: [8, 15, 19, 18, 17, 25, 20]

heapq常用函數

heapq.nlargest(n, data_Set)  #get n largest on data_Set HeapTree
heapq.nsmallest(n, data_Set)  #get n smallest on data_Set HeapTree
In [4]:
## 範例

import heapq

data = [15, 8, 20, 18, 17, 25, 19, 5]
print('Original Data:', data)

largest_number = heapq.nlargest(4, data)
smallest_number = heapq.nsmallest(4, data)
print('Heap Tree中前4個最大的數', largest_number)
print('Heap Tree中前4個最小的數', smallest_number)

Original Data: [15, 8, 20, 18, 17, 25, 19, 5]
Heap Tree中前4個最大的數 [25, 20, 19, 18]
Heap Tree中前4個最小的數 [5, 8, 15, 17]

練習

  • 請自行練習heapq函數

練習

  • heapq預設建構Min Heap, 試想可否透過heapq建構Max Heap?
  • 請撰寫程式對數組15, 8, 20, 18, 17, 25, 19, 5建構Max Heap

Heap Tree的Big O

  • 建構Heap Tree:O(log n)
  • 取出Max Heap或Min Heap最大或最小值:O(1)
  • 取出最大或最小值後再調整為Heap Tree:O(log n)