這天小櫻、知世、小狼、莓玲四個人一同出遊，但是因為「堆」庫洛牌的關係，導致知世、小狼、小櫻依序像吸毒一樣出現了幻覺。第二季換小狼一直發春，看到小櫻就臉紅~~

堆是什麼？

堆像鏈結串列、堆疊、佇列、樹、圖一樣，也是一種資料結構。雖然堆跟堆疊聽起來很像但他們是完全不一樣的東西。

要比的話堆倒是比較像樹。堆可以用來做什麼？

假設現在有一組動態的數字陣列(切片)，隨時會有新的數字加入，也有舊的數字退出，這些數字有的大有的小。如果想要隨時掌握最大值，或是前五個最大值，那麼要選用什麼資料結構來實作最有效率？

如果使用陣列(切片)，每次有舊的數字移出時，就重新產生陣列，然後將整個陣列(切片)做排序。但是這樣會造成電腦很大的負荷，因為排序要付出的時間代價太大了。但如果在這個情況使用堆能有更好的效能

堆其實棵特別的樹

我們以最大堆積來說，最大堆積(Max heap)的實作其實就是棵「父母節點比兒女節點的值還要大的完全二元樹(Complete binary tree)」

先前介紹樹時，僅介紹了二元樹，二元樹的定義是每個父母節點最多只能有兩個兒女節點，而「完全二元樹」的定義就更多了，他不但規定每個父母節點最多只能有兩個節點外，還規定除了最後一層之外，每一層都要填好填滿，而且最後一層一定要有左到右填。

舉個例子，以下這幾種都是「完全二元樹」：

為什麼要規定這麼多呢？因為如此一來這種樣子的「樹」可以不必用指標的方式去實作，而是可以用陣列(切片)去表示，而且會有很特別的特性

我們可以利用陣列的第 1 個索引記錄根節點，第 2 個索引記錄根節點的左子點，第 3 個索引記錄根節點的右子點

注意要從 1 開始，不是 0

這樣有什麼特性呢？首先，如果我想要取得某子點的左子點，那麼只要把現在的索引乘以 2 就行了，如果要得到右子點，就乘以 2 再加 1 就行了。除此之外，如果我要得到父母節點，那麼只要除以 2 就行了 (例如4/2=2, 5/2=2)

了解完「完全二完樹」後，回到「最大堆積」來，最大堆積必需滿足「父母節點比兒女節點的值還要大的」特性

舉個例子：

• 根節點 8，比左子點 4, 右子點 3 都還來的大
• 節點 4 比左子點 1， 右子點 2 都還來的大
• 節點 3 比左子點 -1，右子點 -5 都還來的大
  這樣就是一個最大堆積

取得最大值

從最大堆積取得最大值只要看根節點就好了，因為第一層一定比第二層大，第二層一定比第三層大...，所以最上面的根節點一定就是最大的數字

取得第二大的值

那麼要怎麼取得第二大的值，要取得第二大的值只要把最大值先拔除，再乾坤大挪移一下就可了，至於要怎麼乾坤大挪移，可以先想一下，只要把最後一個節點補回去，那麼結構就會變回原本的樣子了

是完全二元樹沒錯，但是這不是堆啊！！

所以這時只要讓 -5 往下交換一下就可以了

首先先跟他的左右子點中最大的交換

再來如法炮製往下換

如此一來又變回「最大堆積了」

而且最大值又是出現在頂點

我們一般稱這種方法叫 sink (下沉)

增加新的值

假如今天要增加新的值要怎麼增加呢？

如同先前的移除一個值一樣，我們要先滿足「完全二元樹」的特性，將新的值放入最適合的地方(就是最後那個點的右邊啦，如果那一層滿了就往下一層放)

接著跟父母節點做比較，如果自己比較大，就跟父母做交換

你可能會疑惑那如果是另一個子點(手足)比較大咧？傻傻的， 如果另一個子點(手足)比你大，那你父母一定更大啊，那就不用交換了。所以只要跟父母點做比較就可以了，父母點比較大就把他換下來，有一種升遷的概念

這樣子很快就可以變回最大堆積了

我們稱這種方法叫 swim (游)

程式實作

type Heap interface{
    Add(int[])
    Remove(int) int
}

程式實作主要要實現兩個方法「新增」和「移除某一位置」，新增用的技巧是 swim，移除用的方法則是 sink

首先，如同先前資料結構的教學，我們先創建一個 package，至於要怎麼創建？請複習：#14 套件 Package (2020) & 套件實戰(math, http, sort) | Golang魔法使

./heap/heap.go

package heap
import "fmt"
type Heap struct{
    list []int
    last_index int
}

func New() *Heap{
    h := new(Heap)
    
    // 習慣上會先宣告 8 個
    h.list = make([]int, 8)
    
    // h.list[0] = 0
    // 因為[0] 用不到所以隨便填個
    // 其實這一步可以省略
    // 所以我把他註解掉
    
    return h
}

實作 Add() 新增一個節點

func (h *Heap) Add(element int){
    // last_index 一開始預設是 0
    // 要放第一個元素時要先加 1
    // 要從 1 開始放
    
    h.last_index++
    
    // 如果切片不夠長，要記得用 append 的方法
    // 注意 len() 的長度不會貼齊最後一個元素
    // 因為在後面實作移除元素時並沒有去更動長度
    // 因為更動長度挺麻煩的
    if len(h.list) > h.last_index{
        h.list[h.last_index] = element
    }else{
        h.list = append(h.list, element)
    }
    // 將新的元素往上游，游到「適當」的位置
    // 在這裡直接請另一個函式處理
    // 可以增加程式的可讀性
    // 雖然效能會有些許犠牲
    h.swim(h.last_index)
}

實作 Remove(index) 移除特定的一個節點

func (h *Heap) Remove(index int) int{
    // 檢查一下該 index 在不在範圍內
    // 如果不在直接噴錯
    if !(index >= 1 || index < h.last_index){
        panic("欲移除的 index 不在該 heap 內")
    }
    tmp := h.list[index]
    // 把要移除的值用最後一個值來代替
    h.list[index] = h.list[h.last_index]
    // 把指向最後一個的索引減一
    h.last_index--
    // 將已經移除且被替補的那個元素往下沉到適當的位置
    h.sink(index)
    // 回傳被移除的元素
    return tmp
}

實作 swim()，因為該函式只讓本套件使用，沒有要讓引用套件的程式引用的意思(亂用容易出錯)，所以設為小寫開頭

func (h *Heap) swim(index int){
    // 只要現在不是頭點就往上(往父母點)檢查
    for index != 1{
        // 如果父母點比較小就交換
        if h.list[index/2] < h.list[index] {
            h.list[index/2], h.list[index] = h.list[index], h.list[index/2]
        }else{
            // 如果父母點已經比你大了，那就不用往上找了
            // 代表現在這個位置是OK的
            break
        }
        index = index / 2
    }
}

實作 sink()，sink() 比較難實作，因為不但要跟左子點比較，還得和右子點比較

func (h *Heap) sink(index int){
    // 如果沒有左子點，就先不比了，不然會出意外
    // 如果只有左子點，還是可以比，只是要注意不要跟右子點比
    for index*2 <= h.last_index{
        // 要做 sink 前要先確定要和誰比
        // 如果沒有右子點那麼就只和左子點比
        // 如果有左子點也有右子點
            // 左子點比較大，就和左子點比較好了
            // 右子點比較大，就和右子點比較好了

        // 先假設左子點比較大
        j := index*2
        // 如果右子點存在而且比較大再把 j + 1
        if index*2 + 1 <= h.last_index {
            if h.list[index*2 + 1] > h.list[index*2]{
                j++
            }
        }

        // 正式做比較
        // 如果現在的點還是比較小，就做交換
        if h.list[index] < h.list[j] {
            h.list[index], h.list[j] = h.list[j], h.list[index]
            index = j
        }else{
            // 如果現在的點已經比子點都來的大
            // 那麼就可以先離開了
            return
        }
    }
}

因為如果只有單純新增和移除太抽象了，所以實作 Print() 函式，方便觀察

// 把 heap 印出來看看
func (h *Heap) Print(){
    // 分別設定 newline 為 3, 7, 15, 31,...
    // 只要 i 符合，就印換行符號
    newline := 1
    for i := 1; i <= h.last_index; i++{
        fmt.Printf("%d ", h.list[i])
        if i == newline || i== h.last_index{
            fmt.Println()
            newline = newline*2+1
        }
    }
    fmt.Println()
}

實際使用

本教學採用新的套件模式 (go version >= 1.11)
預設 module 名稱是 practice ，所以要 import "practice/heap"

• ./
  • go.mod (利用 go mod init 建立)
  • heap/
    • heap.go (剛剛創建的套件)
  • lesson27.go (準備調用)

./lesson27.go

package main
import(
    "practice/heap"
)

func main(){
    h := heap.New()
    h.Add(-5)
    h.Add(-1)
    h.Add(1)
    h.Add(2)
    h.Add(3)
    h.Add(4)
    h.Add(8)
    h.Print()
    /*
        8
       2 4
    -5 1 -1 3
    */
    h.Remove(7)
    h.Print()
    /*
        8
       2 4
    -5 1 -1
    */
    h.Remove(3)
    h.Print()
    /*
        8
      2 -1
    -5 1
    */
    h.Remove(1)
    h.Print()
    /*
        2
      1 -1
    -5
    */
    h.Remove(1)
    h.Print()
    /*
        1
     -5 -1
    */
    h.Remove(1)
    h.Print()
    /*
        -1
     -5
    */
}

本文圖片大多來自：

• 庫洛魔法使第二季第五集