Golang Heap 源碼剖析

堆原理解析

堆一般指二叉堆。是使用完全二叉樹這種數據結構構建的一種實際應用。通過它的特性，分為最大堆和最小堆兩種。

最大堆和最小堆

如上圖可知，最小堆就是在這顆二叉樹中，任何一個節點的值比其所在子樹的任意一個節點都要小。最大堆就是在這顆二叉樹中，任何一個節點的值都比起所在子樹的任意一個節點值都要大。

那麼如何構建一個堆呢？首先要將所有的元素構建為一個完全二叉樹。完全二叉樹是指除葉子節點，所有層級是滿節點，葉子節點從左向右排列填滿。

在一個完全二叉樹中，將數據重新按照堆的的特性排列，就可以將完全二叉樹變成一個堆。這個過程叫做「堆化」。

在堆中，我們要刪除一個元素一般從堆頂刪除（可以取到最大值/最小值）。刪除之後，數據集就不能算作一個堆了，因為最頂層的元素沒有了，數據集不符合完全二叉樹的定義。這時，我們需要將堆的數據進行重新排列，也就是重新「堆化」。同樣的，在堆中新添加一個元素也需要重新做「堆化」的操作，來將數據集恢復到滿足堆定義的狀態。

所以，在堆這種數據結構中，最重要的是「堆化」的這個演算法操作。其次，堆化數據如何存儲也是很重要的。接下來，詳細說一下。

完全二叉樹的存儲方式

對於二叉樹來說，存儲方式有2種，一種使用數組的形式來存儲，一種使用鏈表的方式存儲。同樣的，這兩種方式繼承了這兩種數據結構的壞處和好處。鏈表的方式相對浪費存儲空間，因為要存儲左右子樹的指針，但擴縮容方便。而數組更加節省空間，更加方便定位節點，缺點則是擴縮容不便。

我們以數組的方式來做示例，了解存儲的細節：

最大堆數組

我們不用 \(index = 0\) 的位置來存儲數據，而是從 \(index = 1\) 開始，這樣，對於任意一個節點 \(i\) 來說，就有 左節點 \(2*i\)，右節點 \(2*i+1\)，而父節點就是 \(\frac i 2\)。

堆的操作

我們先介紹兩種常用的堆操作：pop & push，添加一個元素和刪除一個元素。

假如我們有如下的一個最大堆，當我們添加了一個元素之後，就需要做「堆化」，使得堆滿足定義。

向堆中添加元素

這種從堆底向上堆化的過程，叫做「從下到上堆化」。我把這個過程實現為程式碼，如下：

// 從下到上堆化
func (h *Heap) downToUpHeapify(pos int) {
    for pos / 2 > 0 && h.data[pos/2].Less(h.data[pos]) { // 如果存在父節點 & 值大於父節點
        h.swap(pos, pos/2) // 交換兩個值的位置
        pos = pos /2 // 將操作節點變為父節點的位置
    }
}

當我們想要從堆頂 pop 一個元素的時候。我們需要先將元素pop，然後把堆中最後一個元素放到堆頂，然後進行一次「堆化」。

從堆中彈出元素

這種從堆頂向下堆化的過程，叫做「從上到下堆化」。我把這個過程實現為程式碼，如下：

// 從上到下堆化
func (h *Heap) upToDownHeapify() {
    max := h.len
    i := 1
    pos := i
    for {
        if i * 2 <= max && h.data[i].Less(h.data[i*2]) { // 如果有左子樹，且自己小於左子樹
            pos = i*2 
        }

        if i *2 +1 <= max && h.data[pos].Less(h.data[i*2+1]) { // 如果有右子樹，且自己小於右子樹
            pos = i*2+1
        }
        if pos == i { // 如果位置沒有變化，說明堆化結束
            break
        }

        h.swap(i, pos) // 交換當前位置和下一個位置的內容
        i = pos // 操作下一個位置
    }
}

Golang 的 container.heap 包

注意，上述的講述中，為了方便表示，我們在數組的索引0沒有存儲內容，從索引1開始存儲。

而 Golang 的實現中，索引0 是存儲了數據的。這樣的話，每一個元素的左子樹和右子樹就分別變成了 \(2*i+1\) 和 \(2*i+2\)。

Golang 的 Container.heap 是一個實現了通用最小堆的包。任何數據集只要實現了其 Interface 介面，即可使用這個包將其堆化，並進行一系列的操作。

type Interface interface {
    sort.Interface
  Push(x interface{}) // 把元素添加到 Len() 的位置
    Pop() interface{}   // 刪除並返回 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)
}

Interface 的數據結構如上，要求實現 sort.Interface 和 Push Pop 兩個方法。

sort.Interface 的定義，同樣貼在了上面，主要是三個方法：

  • Len 返回數據集的長度；
  • Less 返回 index i 是否小於 index j；
  • Swap 交換 index i 和 j 的值；

接下來，我們看一下 Push 操作：

func Push(h Interface, x interface{}) {
    h.Push(x) // 向數據集添加一個元素
    up(h, h.Len()-1) // 從下向上堆化
}

// 從下向上堆化的內容
func up(h Interface, j int) {
  // h 表示堆，j 代表需要堆化的元素 index
    for {
        i := (j - 1) / 2 // 定義 j 的父 index
        if i == j || !h.Less(j, i) { // 如果兩個元素相等 或者 父元素小於當前元素
            break  // 堆化完成
        }
        h.Swap(i, j) // 交換父元素和當前元素
        j = i // index 變為父元素的 index
    }
}

上面在 push 元素之後，做了 「從下到上」的堆化。

接下來，是 Pop 操作：

// 返回堆頂的元素，並刪掉它
func Pop(h Interface) interface{} {
  n := h.Len() - 1 // 獲取最終堆長度（去掉最後一個元素）
    h.Swap(0, n)     // 交換堆頂和最後一個元素
    down(h, 0, n)    // 從上到下堆化
    return h.Pop()   // 彈出最後一個元素
}

func down(h Interface, i0, n int) bool {
    i := i0 // 堆頂 index
    for {
        j1 := 2*i + 1  // 左孩子 index
        if j1 >= n || j1 < 0 { // j1 大於堆長度 或 溢出
            break  // 堆化結束
        }
        j := j1 // j = 左孩子
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { 
      // j2 = 右孩子；j 小於堆長度 && 右孩子小於左孩子
            j = j2 // j = 2*i + 2 = 右孩子 
        }
    // 上面是從左右孩子選出小的那個，將 index 賦值給 j
    
        if !h.Less(j, i) { // 如果 堆頂小於 j , 堆化結束
            break
        }
    
        h.Swap(i, j) // 交換堆頂元素和 j
        i = j // 切換到下一個操作 index
    }
  
  // 返回 元素是否有移動
  // 此處是一個特殊設計，用來判斷向下堆化是否真的有操作
  // 當刪除中間的元素時，如果向下堆化沒有操作的話，就需要再做向上堆化
    return i > i0 
}

Golang 還提供了之前原理講述中沒有的方法： Remove Fix

  • Remove 是刪除堆中指定元素，不一定是堆頂；
  • Fix 是當某一個元素的值有變化時，用來重新堆化；
func Remove(h Interface, i int) interface{} {
    n := h.Len() - 1 // 堆的長度
    if n != i { // 如果不是堆頂
        h.Swap(i, n) // 交換刪除元素 和 最後一個元素
        if !down(h, i, n) { // 從上到下堆化
            up(h, i) // 如果沒有成功，就從下島上堆化
        }
    }
    return h.Pop() // 彈出最後一個元素
}

func Fix(h Interface, i int) {
  // i 是值被改變的 index
    if !down(h, i, h.Len()) {   // 從上到下堆化
        up(h, i) // 如果沒有成功，就從下島上堆化
    }
}

這裡有一個內容需要注意，就是 Remove 中， \(n = Len() -1\) 來表示堆長度，而在 Fix 則使用 \(n = Len()\) 來表示。這是因為 Remove 中，最後一個元素是要被刪除掉，所以最終的堆長度是 \(Len() – 1\)。

上面我們已經了解了 Golang 中，對於一個堆的所有操作。只剩下最後一個方法：Init，初始化一個數據集，變成堆。

func Init(h Interface) {
    n := h.Len()  // n 是堆長度
  // i = 最後一個非葉子節點的 index； i >= 堆頂； index 自減
    for i := n/2 - 1; i >= 0; i-- {
    // 從當前節點開始，從上到下堆化
        down(h, i, n)
    }
}

根據堆的特性可知，葉子節點不可以從上到下堆化。所以，我們找到最後非葉子節點的索引值，從這裡開始做堆化操作。

至此，container.heap 包中的內容就全部講解完畢。了解了堆的原理之後，其實會發現並不難理解。

堆的應用

在堆排序中，就需要用到堆演算法來將數據級堆化，然後一個個的彈出元素，以達到排序的目的。

堆也可以用於實現優先順序隊列。優先順序隊列在實際開發過程中有著廣泛的應用。在很多時候，都可以用它來實現處理帶優先順序的事件，處理定時任務等等。

Tags:

VirMach 便宜 VPS

QNews

QNews