?聲明，本文部分內容摘自：

?Go: 深入理解堆實現及應用-騰訊云開發者社區-騰訊云

數組實現堆 | WXue

堆（Heap）是實現優先隊列的數據結構，Go提供了接口和方法來操作堆。

應用

package mainimport ("container/heap""sort"
)/*
題目：給你一個整數數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字，滑動窗口每次只向右移動一位，返回滑動窗口中的最大值。示例：輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3輸出：[3,3,5,5,6,7]解釋：滑動窗口的位置                最大值---------------------------------[1 3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7
題解：大根堆可以幫助我們實時維護一系列元素中的最大值。初始時，我們將數組 nums 的前 k 個元素放入優先隊列中。每當我們向右移動窗口時，我們就可以把一個新的元素放入優先隊列中，此時堆頂的元素就是堆中所有元素的最大值。然而這個最大值可能并不在滑動窗口中，在這種情況下，這個值在數組 nums 中的位置出現在滑動窗口左邊界的左側。因此，當我們后續繼續向右移動窗口時，這個值就永遠不可能出現在滑動窗口中了，我們可以將其永久地從優先隊列中移除。我們不斷地移除堆頂的元素，直到其確實出現在滑動窗口中。此時，堆頂元素就是滑動窗口中的最大值。為了方便判斷堆頂元素與滑動窗口的位置關系，我們可以在優先隊列中存儲二元組 (num,index)，表示元素 num 在數組中的下標為 index。
*/var a []int// heap 實現了標準庫的heap.Interface接口
type hp struct {sort.IntSlice // type IntSlice []int
}func (h hp) Less(i, j int) bool {return a[h.IntSlice[i]] > a[h.IntSlice[j]]
}
func (h *hp) Push(v interface{}) {h.IntSlice = append(h.IntSlice, v.(int))
}
func (h *hp) Pop() interface{} {a := h.IntSlicev := a[len(a)-1]h.IntSlice = a[:len(a)-1]return v
}func maxSlidingWindow(nums []int, k int) (ans []int) {ans = make([]int, 1, len(nums)-k+1)a = nums// 初始化堆（優先隊列）queue := &hp{make([]int, k)} // 優先隊列for i := 0; i < k; i++ {queue.IntSlice[i] = i // 注意堆里存的是數組下標而非數組值，對應Less函數里的比較時需要a[h.IntSlice[i]]來比較值}heap.Init(queue) // 初始化+向下調整// 賦值ans[0]，因為不需要判斷IntSlice[0]的元素是不是在邊界外的左側ans[0] = nums[queue.IntSlice[0]] // IntSlice[0] 下標為0=數組IntSlice的頭部=堆頂元素// 窗口滑動for i := k; i < len(nums); i++ {heap.Push(queue, i)            // 入堆+向上調整for queue.IntSlice[0] <= i-k { // 判斷IntSlice[0]的元素是不是在邊界外的左側heap.Pop(queue) // 出堆+向下調整}ans = append(ans, nums[queue.IntSlice[0]]) // IntSlice[0] 下標為0=數組頭部=堆頂元素}return ans
}func main() {res := maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3)println(res)
}

底層

包：container/heap

接口：heap.Interface

源碼：

type Interface interface {sort.InterfacePush(x interface{}) // 添加元素Pop() interface{}   // 彈出元素
}

其中，注意，實現heap.Interface接口需要嵌入sort.Interface，后者包含Len()、Less(i, j int) bool和Swap(i, j int)方法，用于確定元素間的排序。

全部源碼：

type Interface interface {sort.InterfacePush(x any) // add x as element Len()Pop() any   // remove and return element Len() - 1.
}func Init(h Interface) {// heapifyn := h.Len()for i := n/2 - 1; i >= 0; i-- {down(h, i, n)}
}// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x any) {h.Push(x)up(h, h.Len()-1)
}func Pop(h Interface) any {n := h.Len() - 1h.Swap(0, n)down(h, 0, n)return h.Pop()
}func Remove(h Interface, i int) any {n := h.Len() - 1if n != i {h.Swap(i, n)if !down(h, i, n) {up(h, i)}}return h.Pop()
}func Fix(h Interface, i int) {if !down(h, i, h.Len()) {up(h, i)}
}func up(h Interface, j int) {for {i := (j - 1) / 2 // parentif i == j || !h.Less(j, i) {break}h.Swap(i, j)j = i}
}func down(h Interface, i0, n int) bool {i := i0for {j1 := 2*i + 1if j1 >= n || j1 < 0 { // j1 < 0 after int overflowbreak}j := j1 // left childif j2 := j1 + 1; j2 < n && h.Less(j2, j1) {j = j2 // = 2*i + 2  // right child}if !h.Less(j, i) {break}h.Swap(i, j)i = j}return i > i0
}

其中：

? ? ① 初始化（Init）： 對一個未排序的切片構建堆。這是通過down方法實現的，down方法確保元素下沉到正確的位置，維持堆的性質。

? ? ② 添加元素（Push）： 元素被添加到切片的末尾，然后通過up方法上浮到正確的位置。

注意：標準庫中的push函數中，第一行調用的【h.Push(x)】是上層業務代碼中自行實現的heap.Interface的堆實例的push方法。

func Push(h Interface, x any) {
?? ?h.Push(x)
?? ?up(h, h.Len()-1)
}

? ? ③ 刪除元素（Pop）： 堆頂元素（切片的第一個元素）被移動到切片末尾并返回，然后新的堆頂元素通過down方法恢復堆的性質。

? ? ④ 刪除任意元素（Remove）： 類似Pop，但可以移除指定位置的元素。此操作需要綜合up和down方法來調整堆。

? ? ⑤ 修改元素并調整堆（Fix）： 如果堆中某個元素被外部修改了（比如優先級改變），Fix方法會根據這個修改后的新值重新調整堆。

堆是一顆完全二叉樹，可由數組表示

完全二叉樹，逐層而下，從左到右，結點的位置完全由其序號覺得，因此可以用數組來實現。

計算各結點下標的公式，其中?𝑟𝑟?表示結點的下標，范圍在 0 ~ n-1 之間，n 是二叉樹結點的總數。

𝑃𝑎𝑟𝑒𝑛𝑡(𝑟)=?(𝑟?1)/2?𝑃𝑎𝑟𝑒𝑛𝑡(𝑟)=?(𝑟?1)/2??向下取整，當?𝑟≠0𝑟≠0?時

𝐿𝑒𝑓𝑡𝑐?𝑖𝑙𝑑(𝑟)=2𝑟+1𝐿𝑒𝑓𝑡𝑐?𝑖𝑙𝑑(𝑟)=2𝑟+1, 當?2𝑟+1<𝑛2𝑟+1<𝑛?時

𝑅𝑖𝑔?𝑡𝑐?𝑖𝑙𝑑(𝑟)=2𝑟+2𝑅𝑖𝑔?𝑡𝑐?𝑖𝑙𝑑(𝑟)=2𝑟+2, 當?2𝑟+2<𝑛2𝑟+2<𝑛?時

𝐿𝑒𝑓𝑡𝑠𝑖𝑏𝑙𝑖𝑛𝑔()=𝑟?1𝐿𝑒𝑓𝑡𝑠𝑖𝑏𝑙𝑖𝑛𝑔()=𝑟?1, 當 r 為偶數時

𝑅𝑖𝑔?𝑡𝑠𝑖𝑏𝑙𝑖𝑛𝑔()=𝑟+1𝑅𝑖𝑔?𝑡𝑠𝑖𝑏𝑙𝑖𝑛𝑔()=𝑟+1?, 當 r 為奇數并且?𝑟+1<𝑛𝑟+1<𝑛?時

插入數值：在堆的末尾插入，然后不斷向上提升，直到沒有大小顛倒。

刪除數值：首先把堆的最后一個節點的數值放到根上去，并且刪除最后一個節點，然后不斷向下交換直到沒有大小顛倒為止。向下交換的時候如果 2 個兒子都比自己小，那么選擇數值較小的兒子進行交換。

復雜度：建堆需要 On?的時間，但刪除、插入都和樹深度成正比，時間復雜度是 O𝑛𝑙𝑜𝑔𝑛。