關於用 Go 實現堆和堆操作，可能是最通俗易懂的講解了

堆是一種樹形數據結構，分爲大頂堆和小頂堆，顧名思義，大頂堆就是堆頂（第一個元素）始終存放的是這組元素中的最大元素，小頂堆就是堆頂元素是最小元素。如果需要從一組對象中查找最大值或最小值，使用堆能夠高效率的完成需求。

排序算法中的堆排序正是利用了堆這一數據完成的排序，堆在實際應用中主要被用於實現優先隊列（priority queue）下面我們以小頂堆爲例學習一下堆的結構和常規操作。

堆的特性

小頂堆

如上圖所示，就是一個小頂堆，我們先來說說它的特性。

完全二叉樹

首先堆是一棵完全二叉樹，關於完全二叉樹和滿二叉樹：

如果一個二叉樹的任何節點，要麼是葉子節點，要麼左右子樹均非空，則這棵二叉樹稱做滿二叉樹（full binary tree）

如果一個二叉樹最多隻有最下面的兩層節點度數可以小於 2，並且最下面一層的節點都集中在該層最左邊的連續位置上，則此二叉樹稱做完全二叉樹（complete binary tree）

滿二叉樹和完全二叉樹

節點的規則

在小頂堆中存儲數據時必須遵守這樣一條規則 ：堆中所有節點的值均不大於其左右子節點的值，一個節點與其兄弟節點之間沒有必然的聯繫。

而在二叉查找樹中是，左子 < 父 < 右子

存儲結構

由於堆是一棵完全二叉樹，可以用數組來存儲，只需要通過簡單的代數表達式，就能計算出要某個節點的父節點和子節點的索引位置，既避免了像鏈表那樣使用指針來保持結構，又能高效的執行相應操作。

關於節點的父節點和子節點在堆中的位置需要記住下面三個公式：

C 在數組中索引爲 2，左子爲 22+1=5，右子爲 22+2=6

用 Go 實現堆操作

上面我們分析完堆的特性和存儲結構後，我們自己用 Go 語言實現一個堆以及堆的各種操作。

數據結構

type Heap []int

// 交換兩個節點的值
func (h Heap) swap(i, j int) {
 h[i], h[j] = h[j], h[i]
}

// 比較兩個節點的值
func (h Heap) less(i, j int) bool {
  // 如果實現的是大頂堆，修改這裏的判斷即可
 return h[i] < h[j]
}

上面我們定義了小頂堆的數據結構以及它的兩個基本操作，比較以及交換兩個節點的值。下面來實現堆結構上的常規操作。

插入

向堆中插入數據時，首先會把元素放到末尾。如下圖所示，向小頂堆中插入一個值爲 5 的節點

向堆中插入一個新節點

先把節點放到了堆的末尾

先插入到堆的末尾

末尾插入新節點後，不再滿足小頂堆的要求，故需要沿着其路徑，自下而上依次比較和交換該節點與父節點的位置，直到重新滿足小頂堆的性質爲止。

5>6，不滿足父節點必須小於等於子節點的性質，交換之

交換位置後，再比較發現比父節點大了，停止交換

如上圖所示，首先，新添加的節點加入到末尾。爲了保持小頂堆的性質，需要讓該節點沿着其路徑，自下而上依次比較和交換自身與父節點點的位置，直到重新滿足小頂堆的性質爲止。

這樣會出現兩種情況，要麼新節點一直升到堆頂，要麼到某一位置時發現父節點比自己小，則停止。

上面的流程代碼如下：

func (h Heap) up(i int) {
 for {
  f := (i - 1) / 2 // 父節點在數組中的位置
  if i == f || h.less(f, i) {
   break
  }
  h.swap(f, i)
  i = f
 }
}

// 注意go中所有參數都是值傳遞
// 所以要讓h的變化在函數外也起作用，此處要傳指針
func (h *Heap) Push(x int) {
 *h = append(*h, x)
 h.up(len(*h) - 1)
}

刪除

從最小堆中刪除節點，分爲以下三個步驟

與子節點進行比較交換的 down 操作的流程用代碼表示爲：

func (h Heap) down(i int) {
 for {
  l := 2*i + 1 // 左孩子
  r := 2*i +2 // 右孩子
  if l >= len(h) {
   break // i 已經是葉子節點，退出操作。
  }
  j := l
  if r < len(h) && h.less(r, l) {
   j = r // 右孩子爲最小子節點
  }
  // i 與最小子節點進行比較 
  if h.less(i, j) {
   break // 如果父節點比子節點小，則不交換
  }
  h.swap(i, j) // 交換父子節點
  i = j        //繼續向下比較
 }
}

實現了核心的up 和down 操作後，堆的Remove操作便很簡單，代碼如下：

// 刪除堆中位置爲i的元素
// 返回被刪元素的值
func (h *Heap) Remove(i int) (int, bool) {
 if i < 0 || i > len(*h)-1 {
  return 0, false
 }
 n := len(*h) - 1
 h.swap(i, n) // 用最後的元素值替換被刪除元素
 // 刪除最後的元素
 x := (*h)[n]
 *h = (*h)[0:n]
 // 如果當前元素大於父節點，向下篩選
 if i == 0 || (*h)[i] > (*h)[(i-1)/2] {
  h.down(i)
 } else { // 當前元素小於父節點，向上篩選
  h.up(i)
 }
 return x, true
}

彈出堆頂元素

彈出堆頂元素，就是刪除 i = 0 的節點。

// 彈出堆頂的元素，並返回其值
func (h *Heap) Pop() int {
  x, _ := h.Remove(0)
  return x
}

建堆

講完了堆的核心操作 up 和 down 後，我們來看一下如何根據一個數組構造一個小頂堆。

建立堆的過程就是完全二叉樹，從下到上調整堆的過程，從 i = len(arr) /2 開始依次向上調整，i = len(arr) /2是堆中末尾節點的父節點， i=0是根節點。

func BuildHeap(arr []int) Heap {
 h := Heap(arr)
 n := len(h)
  // 從第一個非葉子節點，到根節點
  for i := n/2 - 1; i >= 0; i-- {
  h.down(i)
 }

 return h
}

堆排序

學完堆的基礎知識後，我們再來看堆排序就變得非常簡單。利用最小堆的特性，我們每次都從堆頂彈出一個元素（這個元素就是當前堆中的最小值），即可實現升序排序。代碼如下：

func HeapSort(arr []int) {
  // 創建堆
 heap := BuildHeap(arr)
 var sortedArr []int
 for len(heap) > 0 {
  sortedArr = append(sortedArr, heap.Pop())
 }

 fmt.Println(sortedArr)
}

func main() {
 //輸出 [3 8 10 15 15 16 17 19 24 30 33]
  HeapSort([]int{33, 24, 8, 3, 10, 15, 16, 15, 30, 17, 19}) 
}

Go 標準庫對堆的定義

堆是一種很好的實現優先隊列的數據結構，我們在這裏自己實現了一個小頂堆。Go 在它的標準庫 container/heap 也提供了堆的定義，

type Interface interface {
 sort.Interface
 Push(x any) // add x as element Len()
 Pop() any   // remove and return element Len() - 1.
}

它匿名嵌套的 sort.Interface 的定義如下：

type Interface interface {
 // Len is the number of elements in the collection.
 Len() int
 // Less reports whether the element with
 // index i should sort before the element with index j.
 Less(i, j int) bool
 // Swap swaps the elements with indexes i and j.
 Swap(i, j int)
}

也就是說，我們要使用go標準庫給我們提供的heap，那麼必須自己實現上面兩個接口定義的方法，這些方法的實現方式就是我們上面演示的建堆、插入、刪除這些操作，這裏就不再繼續演示 Go 這個 heap 庫的使用啦。

參考

網管叨 bi 叨 分享軟件開發和系統架構設計基礎、Go 語言和 Kubernetes。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/jkHoVL6Ex93WuTr4lUaAJg

猜你喜歡