堆原理解析

堆一般指二叉堆。是使用完全二叉樹(shù)這種數(shù)據(jù)結(jié)構(gòu)構(gòu)建的一種實(shí)際應(yīng)用。通過(guò)它的特性，分為最大堆和最小堆兩種。

如上圖可知，最小堆就是在這顆二叉樹(shù)中，任何一個(gè)節(jié)點(diǎn)的值比其所在子樹(shù)的任意一個(gè)節(jié)點(diǎn)都要小。最大堆就是在這顆二叉樹(shù)中，任何一個(gè)節(jié)點(diǎn)的值都比起所在子樹(shù)的任意一個(gè)節(jié)點(diǎn)值都要大。

那么如何構(gòu)建一個(gè)堆呢？首先要將所有的元素構(gòu)建為一個(gè)完全二叉樹(shù)。完全二叉樹(shù)是指除葉子節(jié)點(diǎn)，所有層級(jí)是滿節(jié)點(diǎn)，葉子節(jié)點(diǎn)從左向右排列填滿。

在一個(gè)完全二叉樹(shù)中，將數(shù)據(jù)重新按照堆的的特性排列，就可以將完全二叉樹(shù)變成一個(gè)堆。這個(gè)過(guò)程叫做“堆化”。

在堆中，我們要?jiǎng)h除一個(gè)元素一般從堆頂刪除（可以取到最大值/最小值）。刪除之后，數(shù)據(jù)集就不能算作一個(gè)堆了，因?yàn)樽铐攲拥脑貨](méi)有了，數(shù)據(jù)集不符合完全二叉樹(shù)的定義。這時(shí)，我們需要將堆的數(shù)據(jù)進(jìn)行重新排列，也就是重新“堆化”。同樣的，在堆中新添加一個(gè)元素也需要重新做“堆化”的操作，來(lái)將數(shù)據(jù)集恢復(fù)到滿足堆定義的狀態(tài)。

所以，在堆這種數(shù)據(jù)結(jié)構(gòu)中，最重要的是“堆化”的這個(gè)算法操作。其次，堆化數(shù)據(jù)如何存儲(chǔ)也是很重要的。接下來(lái)，詳細(xì)說(shuō)一下。

完全二叉樹(shù)的存儲(chǔ)方式

對(duì)于二叉樹(shù)來(lái)說(shuō)，存儲(chǔ)方式有2種，一種使用數(shù)組的形式來(lái)存儲(chǔ)，一種使用鏈表的方式存儲(chǔ)。同樣的，這兩種方式繼承了這兩種數(shù)據(jù)結(jié)構(gòu)的壞處和好處。鏈表的方式相對(duì)浪費(fèi)存儲(chǔ)空間，因?yàn)橐鎯?chǔ)左右子樹(shù)的指針，但擴(kuò)縮容方便。而數(shù)組更加節(jié)省空間，更加方便定位節(jié)點(diǎn)，缺點(diǎn)則是擴(kuò)縮容不便。

我們以數(shù)組的方式來(lái)做示例，了解存儲(chǔ)的細(xì)節(jié)：

我們不用 (index = 0) 的位置來(lái)存儲(chǔ)數(shù)據(jù)，而是從 (index = 1) 開(kāi)始，這樣，對(duì)于任意一個(gè)節(jié)點(diǎn) (i) 來(lái)說(shuō)，就有 左節(jié)點(diǎn) (2i)，右節(jié)點(diǎn) (2i+1)，而父節(jié)點(diǎn)就是 (\frac i 2)。

堆的操作

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

假如我們有如下的一個(gè)最大堆，當(dāng)我們添加了一個(gè)元素之后，就需要做“堆化”，使得堆滿足定義。

這種從堆底向上堆化的過(guò)程，叫做“從下到上堆化”。我把這個(gè)過(guò)程實(shí)現(xiàn)為代碼，如下：

// 從下到上堆化
func (h *Heap) downToUpHeapify(pos int) {
    for pos / 2 > 0 && h.data[pos/2].Less(h.data[pos]) { // 如果存在父節(jié)點(diǎn) & 值大于父節(jié)點(diǎn)
        h.swap(pos, pos/2) // 交換兩個(gè)值的位置
        pos = pos /2 // 將操作節(jié)點(diǎn)變?yōu)楦腹?jié)點(diǎn)的位置
    }
}

當(dāng)我們想要從堆頂 pop 一個(gè)元素的時(shí)候。我們需要先將元素pop，然后把堆中最后一個(gè)元素放到堆頂，然后進(jìn)行一次“堆化”。

這種從堆頂向下堆化的過(guò)程，叫做“從上到下堆化”。我把這個(gè)過(guò)程實(shí)現(xiàn)為代碼，如下：

// 從上到下堆化
func (h *Heap) upToDownHeapify() {
    max := h.len
    i := 1
    pos := i
    for {
        if i * 2 <= max && h.data[i].Less(h.data[i*2]) { // 如果有左子樹(shù)，且自己小于左子樹(shù)
            pos = i*2 
        }
        if i *2 +1 <= max && h.data[pos].Less(h.data[i*2+1]) { // 如果有右子樹(shù)，且自己小于右子樹(shù)
            pos = i*2+1
        }
        if pos == i { // 如果位置沒(méi)有變化，說(shuō)明堆化結(jié)束
            break
        }
        h.swap(i, pos) // 交換當(dāng)前位置和下一個(gè)位置的內(nèi)容
        i = pos // 操作下一個(gè)位置
    }
}

Golang 的 container.heap 包

注意，上述的講述中，為了方便表示，我們?cè)跀?shù)組的索引0沒(méi)有存儲(chǔ)內(nèi)容，從索引1開(kāi)始存儲(chǔ)。 而 Golang 的實(shí)現(xiàn)中，索引0 是存儲(chǔ)了數(shù)據(jù)的。這樣的話，每一個(gè)元素的左子樹(shù)和右子樹(shù)就分別變成了 (2i+1) 和 (2i+2)。

Golang 的 Container.heap 是一個(gè)實(shí)現(xiàn)了通用最小堆的包。任何數(shù)據(jù)集只要實(shí)現(xiàn)了其 Interface 接口，即可使用這個(gè)包將其堆化，并進(jìn)行一系列的操作。

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 的數(shù)據(jù)結(jié)構(gòu)如上，要求實(shí)現(xiàn) sort.Interface 和 Push Pop 兩個(gè)方法。

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

• Len 返回?cái)?shù)據(jù)集的長(zhǎng)度；
• Less 返回 index i 是否小于 index j；
• Swap 交換 index i 和 j 的值；

接下來(lái)，我們看一下 Push 操作：

func Push(h Interface, x interface{}) {
    h.Push(x) // 向數(shù)據(jù)集添加一個(gè)元素
    up(h, h.Len()-1) // 從下向上堆化
}
// 從下向上堆化的內(nèi)容
func up(h Interface, j int) {
  // h 表示堆，j 代表需要堆化的元素 index
    for {
        i := (j - 1) / 2 // 定義 j 的父 index
        if i == j || !h.Less(j, i) { // 如果兩個(gè)元素相等 或者 父元素小于當(dāng)前元素
            break  // 堆化完成
        }
        h.Swap(i, j) // 交換父元素和當(dāng)前元素
        j = i // index 變?yōu)楦冈氐?index
    }
}

上面在 push 元素之后，做了 “從下到上”的堆化。

接下來(lái)，是 Pop 操作：

// 返回堆頂?shù)脑兀h掉它
func Pop(h Interface) interface{} {
  n := h.Len() - 1 // 獲取最終堆長(zhǎng)度（去掉最后一個(gè)元素）
    h.Swap(0, n)     // 交換堆頂和最后一個(gè)元素
    down(h, 0, n)    // 從上到下堆化
    return h.Pop()   // 彈出最后一個(gè)元素
}
func down(h Interface, i0, n int) bool {
    i := i0 // 堆頂 index
    for {
        j1 := 2*i + 1  // 左孩子 index
        if j1 >= n || j1 < 0 { // j1 大于堆長(zhǎng)度 或 溢出
            break  // 堆化結(jié)束
        }
        j := j1 // j = 左孩子
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { 
      // j2 = 右孩子；j 小于堆長(zhǎng)度 && 右孩子小于左孩子
            j = j2 // j = 2*i + 2 = 右孩子 
        }
    // 上面是從左右孩子選出小的那個(gè)，將 index 賦值給 j
        if !h.Less(j, i) { // 如果 堆頂小于 j , 堆化結(jié)束
            break
        }
        h.Swap(i, j) // 交換堆頂元素和 j
        i = j // 切換到下一個(gè)操作 index
    }
  // 返回 元素是否有移動(dòng)
  // 此處是一個(gè)特殊設(shè)計(jì)，用來(lái)判斷向下堆化是否真的有操作
  // 當(dāng)刪除中間的元素時(shí)，如果向下堆化沒(méi)有操作的話，就需要再做向上堆化
    return i > i0 
}

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

• Remove 是刪除堆中指定元素，不一定是堆頂；
• Fix 是當(dāng)某一個(gè)元素的值有變化時(shí)，用來(lái)重新堆化；

func Remove(h Interface, i int) interface{} {
    n := h.Len() - 1 // 堆的長(zhǎng)度
    if n != i { // 如果不是堆頂
        h.Swap(i, n) // 交換刪除元素 和 最后一個(gè)元素
        if !down(h, i, n) { // 從上到下堆化
            up(h, i) // 如果沒(méi)有成功，就從下島上堆化
        }
    }
    return h.Pop() // 彈出最后一個(gè)元素
}
func Fix(h Interface, i int) {
  // i 是值被改變的 index
    if !down(h, i, h.Len()) {   // 從上到下堆化
        up(h, i) // 如果沒(méi)有成功，就從下島上堆化
    }
}

這里有一個(gè)內(nèi)容需要注意，就是 Remove 中， (n = Len() -1) 來(lái)表示堆長(zhǎng)度，而在 Fix 則使用 (n = Len()) 來(lái)表示。這是因?yàn)?Remove 中，最后一個(gè)元素是要被刪除掉，所以最終的堆長(zhǎng)度是 (Len() – 1)。

上面我們已經(jīng)了解了 Golang 中，對(duì)于一個(gè)堆的所有操作。只剩下最后一個(gè)方法：Init，初始化一個(gè)數(shù)據(jù)集，變成堆。

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

根據(jù)堆的特性可知，葉子節(jié)點(diǎn)不可以從上到下堆化。所以，我們找到最后非葉子節(jié)點(diǎn)的索引值，從這里開(kāi)始做堆化操作。

至此，container.heap 包中的內(nèi)容就全部講解完畢。了解了堆的原理之后，其實(shí)會(huì)發(fā)現(xiàn)并不難理解。

堆的應(yīng)用

在堆排序中，就需要用到堆算法來(lái)將數(shù)據(jù)級(jí)堆化，然后一個(gè)個(gè)的彈出元素，以達(dá)到排序的目的。

堆也可以用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。優(yōu)先級(jí)隊(duì)列在實(shí)際開(kāi)發(fā)過(guò)程中有著廣泛的應(yīng)用。在很多時(shí)候，都可以用它來(lái)實(shí)現(xiàn)處理帶優(yōu)先級(jí)的事件，處理定時(shí)任務(wù)等等。

以上就是Golang Heap的源碼剖析的詳細(xì)內(nèi)容，更多關(guān)于Golang Heap的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論