4 堆排 · Tequila's 学习笔记

import (
    "container/heap"
    "fmt"
)
type hp []int

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i] < h[j] }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x any)        { *h = append(*h, x.(int)) }
func (h *hp) Pop() any          { x := (*h)[len(*h)-1]; *h = (*h)[:len(*h)-1]; return x }

函数	描述	时间复杂度
`heap.Init(h)`	初始化一个堆，将任意切片整理成合法的堆结构。	O(n)
`heap.Push(h, x)`	向堆中添加一个新元素。	O(log n)
`heap.Pop(h)`	移除并返回堆顶（即最小或最大）元素。	O(log n)
`heap.Remove(h, i)`	移除堆中指定索引 `i` 的元素并返回。	O(log n)
`heap.Fix(h, i)`	在索引 `i` 处的元素值被修改后，重新恢复堆的顺序。	O(log n)

Reply by Email