Go 數(shù)據(jù)結(jié)構(gòu)之堆排序示例詳解

更新時間：2022年08月26日 15:56:00 作者：宇宙之一粟

這篇文章主要為大家介紹了Go 數(shù)據(jù)結(jié)構(gòu)之堆排序示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

堆排序

堆排序是一種樹形選擇排序算法。

簡單選擇排序算法每次選擇一個關(guān)鍵字最小的記錄需要 O(n) 的時間，而堆排序選擇一個關(guān)鍵字最小的記錄需要 O(nlogn)的時間。

堆可以看作一棵完全二叉樹的順序存儲結(jié)構(gòu)。

在這棵完全二叉樹中，如果每個節(jié)點(diǎn)的值都大于等于左邊孩子的值，稱為大根堆（最大堆、又叫大頂堆）。如果每個節(jié)點(diǎn)的值都小于等于左邊孩子的值，稱為小根堆（最小堆，小頂堆）。

可以，用數(shù)學(xué)符號表示如下：

堆排序過程

構(gòu)建初始堆
在輸出堆的頂層元素后，從上到下進(jìn)行調(diào)整，將頂層元素與其左右子樹的根節(jié)點(diǎn)進(jìn)行比較，并將最小的元素交換到堆的頂部；然后不斷調(diào)整直到葉子節(jié)點(diǎn)得到新的堆。

假如，{1, 7, 9, 2, 4, 6, 3, 5, 8} 建堆，然后進(jìn)行堆排序輸出。

動畫顯示

初始化堆，建堆操作圖畫演示：

首先根據(jù)無序序列 {1, 7, 9, 2, 4, 6, 3, 5, 8} 按照完全二叉樹的順序構(gòu)建一棵完全二叉樹，如圖：

然后從最后一個分支節(jié)點(diǎn) n/2開始調(diào)整堆，這里 9 / 2 = 4:

然后從 n/2−1 開始調(diào)整，即序號 3 開始調(diào)整，接著從 n/2-2 執(zhí)行調(diào)整操作，如圖所示：

一直重復(fù)到序號為 1 的節(jié)點(diǎn)：

最終通過此次調(diào)整堆，得到新的堆為 [9, 8, 6, 7, 4, 1, 3, 5, 2] ，得到新的堆后開始堆排序過程

開始堆排序

構(gòu)建完初始堆后，此時，我們可以進(jìn)入堆排序，從上面的方法中，

我們可以已知我們構(gòu)建的最大堆的堆頂是最大的記錄，可以可以將堆頂交換到最后一個元素的位置，然后執(zhí)行堆頂下沉操作，然后再執(zhí)行堆調(diào)整操作（新的堆頂也是最大值），直到剩余一個節(jié)點(diǎn)，得到一個有序序列。

此時，我們又可以進(jìn)行堆調(diào)整操作，如下圖：

堆調(diào)整完畢，開始把新的堆頂 8 和最后一個記錄 2 進(jìn)行交換，然后將堆頂下沉，調(diào)整為堆，如下圖所示：

從此我們得到新的堆頂 7 ，然后把 7 跟最后一個元素 3 進(jìn)行交換，7 下沉，然后堆調(diào)整，慢慢得到堆頂 6 和堆頂5，如圖所示：

然后是 3 下沉：

最后，堆頂 2 與最后一個記錄 1 進(jìn)行交換，只剩一個節(jié)點(diǎn)，堆排序結(jié)束，如下圖所示：

我們得到的新的序列按序號讀取數(shù)據(jù)，就是一個有序序列。

代碼實(shí)現(xiàn)

最后，我們用代碼來檢驗(yàn)一下我們的動畫過程是否正確，如下：

package main
import "fmt"
// 調(diào)整堆
func adjustHeap(array []int, currentIndex int, maxLength int) {
    var noLeafValue = array[currentIndex] // 當(dāng)前非葉子節(jié)點(diǎn)
    // j 指向左孩子
    // 當(dāng)前非葉子節(jié)點(diǎn)的左節(jié)點(diǎn)為：2 * currentIndex + 1
    for j := 2*currentIndex + 1; j <= maxLength; j = currentIndex*2 + 1 {
        if j < maxLength && array[j] < array[j+1] { // 如果有右孩子，且左孩子比右孩子小
            j++ // j 指向右孩子
        }
        if noLeafValue >= array[j] {
            break // 非葉子節(jié)點(diǎn)大于孩子節(jié)點(diǎn)，跳過不交換
        }
        array[currentIndex] = array[j] // 移動到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
        currentIndex = j               // j 指向交換后的新位置，繼續(xù)向下比較
    }
    array[currentIndex] = noLeafValue // 放在合適的位置
}
// 初始化堆
func createHeap(array []int, length int) {
    // 建堆
    for i := length / 2; i >= 0; i-- {
        adjustHeap(array, i, length-1)
    }
}
func heapSort(array []int, length int) {
    for i := length - 1; i > 0; i-- {
        array[0], array[i] = array[i], array[0]
        adjustHeap(array, 0, i-1)
    }
}
func main() {
    var unsorted = []int{1, 7, 9, 2, 4, 6, 3, 5, 8}
    var length = len(unsorted)
    fmt.Println("建堆之前：")
    for i := 0; i < length; i++ {
        fmt.Printf("%d,", unsorted[i])
    }
    fmt.Println()
    fmt.Println("建堆之后：")
    createHeap(unsorted, length)
    for i := 0; i < length; i++ {
        fmt.Printf("%d,", unsorted[i])
    }
    fmt.Printf("\n堆排序之后: \n")
    heapSort(unsorted, length)
    for i := 0; i < length; i++ {
        fmt.Printf("%d,", unsorted[i])
    }
}

運(yùn)行結(jié)果：

[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 數(shù)據(jù)結(jié)構(gòu)\堆排序\main.go"
建堆之前：
1,7,9,2,4,6,3,5,8,
建堆之后：
9,8,6,7,4,1,3,5,2,
堆排序之后:
1,2,3,4,5,6,7,8,9,

可以看到，創(chuàng)建堆的結(jié)果 9,8,6,7,4,1,3,5,2 和排序結(jié)果 1,2,3,4,5,6,7,8,9 都是和我們圖中的堆一樣，所以說圖看懂了代碼也就變得有意思了。