這天「對」Golang牌出來搞鬼了，什麼東西都變成一對一對。小櫻想嘗試收服，但要同時把兩隻打敗才能收服不然都會封印失敗。此時最有默契的兄妹終於出現啦！！

什麼是 Priority queue?

之前在介紹「佇列」(Queue)時有提到先進先出的概念，就好比排隊，先到的人可以先進場。

但是，有時候有所謂「快速通關」的服務，所謂的快速通關，就是你比別人有更高的優先權。而每個元素有不同「優先權」的佇列，稱為「優先佇列」，不是比誰加入佇列，而是比誰的優先權高。

如果利用「陣列」來實作，那麼每次要找誰有最高的權限時就必需要把所有的元素都看一遍，移除，該元素時還要把後面的元素都往前放。當然，也可以用「鏈結串列」來實現，這樣子比較不會有移動的問題，但是，要找到最大值，也很不容易。而且，如果在過程中，還要加入新的元素，就更麻煩了！

我們可以使用「堆」(Heap)來實作優先佇列：

1. 加入新的元素，要交換最多「$log_2n$」次(swim)
2. 取出最大值時，不需要比較，但要把最後一個元素拿上來做sink 最多要 「$log_2n$」次(swim)

實作 Priority Queue 前先熟悉 heap package

在實作 Priority Queue 前我們先來了解 Go 提供的 heap 套件以方便我們的實作

可以看到 Fix, Init, Pop, Push, Remove 都有以 Interface 為對象所建立的方法，因此要實現 heap 前，要先建立一個可以滿足 heap.Interface 的型態

我們先自訂一個 myHeap 來示範

1. 該型態要先能滿足 sort.Interface{}
2. 實作 Push(x interface{}) 該方法是將 x 添加至 myHeap 的第 Len() 個索引中
3. 實作 Pop() interface{} 該方法是將第 Len() - 1 個元素從 myHeap 中確實移除 (必需要重新更動長度)

Golang 官方範例 (min heap)

// This example demonstrates an integer heap built using the heap interface.
// 該範例演示藉由 heap 介面建立一個「整數(最小)堆積」
package main

import (
    "container/heap"
    "fmt"
)

// An IntHeap is a min-heap of ints.
// 建立自訂型態
type IntHeap []int

// 實作以滿足 sort.Interface 的部分
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    // Push 和 Pop 要透過指標傳值，因為會更動到 slice 的長度而不只是內容
    // 解釋：
    // append 過後的切片可能已經不是本來的切片
    // 所以要透過指標更改 h 的值
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    // 先將要回傳的值暫存起來
    x := old[n-1]
    // 切片重切，因為 heap 套件在內部實作時是
    // 靠切片的長度在定位
    // 跟我們先前的方式不太一樣
    // 所以一定要重切
    *h = old[0 : n-1]
    return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
// 這個範例插入一些整數進入 IntHeap
// 檢查最小值並依權重將他們移除
func main() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h)
	heap.Push(h, 3)
	fmt.Printf("minimum: %d\n", (*h)[0])
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
}

執行結果：
minimum: 1
1 2 3 5

改寫示範 (Max heap)

package main

import(
    "container/heap"
    "fmt"
)

type maxHeap []int

func (h maxHeap) Len() int{ return len(h) }
func (h maxHeap) Swap(i, j int){ h[i], h[j] = h[j], h[i] }
func (h maxHeap) Less(i, j int) bool{
    // heap 預設是實作 min heap
    // 因為我們要實作 max heap
    // 所以把 less 的答案倒轉
    return h[i] > h[j]
}

// Push 要實作的是就是
// 當 heap 新增元素要把新元素加入哪裡 (即 *h[Len(*h)])

func (h *maxHeap) Push(x interface{}){
    *h = append(*h, x.(int))
}

// Pop 要實作的是
// 當有元素被移除時，要用哪一個元素去替補
// 通常都是拿最後一個 (即 *h[Len(*h)-1])
func (h *maxHeap) Pop() interface{}{
    old := *h
    tmp := old[len(*h)-1]
    *h = old[0: len(*h)-1]
    return tmp
}

func main(){
    h := &maxHeap{-5, -1, 1, 2, 3, 4, 8}
    // init 會將初始的值先做成堆
    // 這樣就不用像我們之前實作時得從空陣列(切片)開始加了
    heap.Init(h)
    heap.Push(h, 9)
    fmt.Printf("%d\n", heap.Pop(h))
    fmt.Printf("%d\n", heap.Pop(h))
    fmt.Printf("%d\n", heap.Pop(h))
}

執行結果：
9
8
4

實作 Priority Queue

其中，Priority Queue 要有什麼方法呢？

// 直接來限制使用者加進的元素
type Element struct{
    Val Interface{}    // 任意值
    Priority float64   // 權重(利用 float64 更有彈性)
}

type PQ interface{
    En(*Element)    // 新增元素
    De() *Element   // 返回目前最大的元素
}

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

./pq/pq.go
1. 處理 heap 的部份，並宣告會用到的型態

package pq

import "container/heap"

// 用來維持套件內 heap 的運作
type pqHeap [](*Element)
func (h pqHeap) Len() int{ return len(h) }
func (h pqHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h pqHeap) Less(i, j int) bool { return h[i].Priority > h[j].Priority }

func (h *pqHeap) Push(x interface{}){
    *h = append(*h, x.(*Element))
}

func (h *pqHeap) Pop() interface{}{
    old := *h
    tmp := old[len(*h)-1]
    *h = old[0: len(*h)-1]
    return tmp
}

type Element struct{
    Val interface{}    // 任意值
    Priority float64   // 權重
}

type PQ struct{
    h *pqHeap
    num int             // 計算 heap 內元素個數
}

2. 允許使用者建立新的priority queue 而且可以更簡單的新增 Element

func New() *PQ{
    pq := new(PQ)
    pq.h = &pqHeap{}
    heap.Init(pq.h)
    return pq
}

func NewElement(val interface{}, priority float64) *Element{
    e := new(Element)
    e.Val = val
    e.Priority = priority
    return e
}

3. 實作 En() 和 De()

func (p *PQ) En(e *Element){
    heap.Push(p.h, e)
    p.num++
}

func (p *PQ) De() *Element{
    if p.num == 0{
        return nil
    }
    p.num--
    return heap.Pop(p.h).(*Element)
}

實際調用：

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

• ./
  • go.mod (利用 go mod init 建立)
  • pq/
    • pq.go (剛剛創建的套件)
  • lesson28-2.go (準備調用)

./lseeon28-2.go

package main

import(
    "practice/pq"
    "fmt"
)

func main(){
    // 快速建立優先佇列
    q := pq.New()
    
    // 將值和權重利用 En() 寫入優先佇列
    q.En(pq.NewElement("小櫻", 500.0))
    q.En(pq.NewElement("雪兔", 400.0))
    q.En(pq.NewElement("知世", 600.0))
    q.En(pq.NewElement("小狼", 300.0))
    q.En(pq.NewElement("小可", 100.0))
    q.En(pq.NewElement("莓玲", 200.0))
    
    // 按照權重由大到小從優先佇列移除
    for e := q.De(); e != nil; e = q.De(){
        fmt.Printf("%s (權重：%f)\n", e.Val.(string), e.Priority)
    }
}

執行結果：
知世 (權重：600.000000)
小櫻 (權重：500.000000)
雪兔 (權重：400.000000)
小狼 (權重：300.000000)
莓玲 (權重：200.000000)
小可 (權重：100.000000)

本範例演示如何透過套件的方式，將原先提供的套件做更延伸使用

後記：

這天莓玲要做蛋糕送給小狼，但卻把廚房弄得亂七八遭

為什麼莓玲要做蛋糕給小狼吃呢？因為莓玲即將回去香港。因為小櫻捨不得莓玲離開，於是邀請莓玲到他家過夜。然後小櫻就把小可趕去知世家了

小可ㄎㄧㄤ爆：
搞什麼鬼啊，小丫頭要到家裡住居然把我趕出來
本來我還想好好教訓他們人生的大道理呢
不過算了
這裡有蛋糕吃(知世做的)
而且，又可以欣賞自己的英姿(知世拍的影片)
說實在話，我覺得我自己真帥

因為最後 day29, day30 想把劇情帶到夢境(小結局)那裡，所以中間跳了幾篇~嘿嘿~

本文圖片大多來自：

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