1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// heap
type Interface interface {
	sort.Interface
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

// sort
type Interface interface {
	// Len is the number of elements in the collection.
	Len() int

	// Less reports whether the element with index i
	// must sort before the element with index j.
	//
	// If both Less(i, j) and Less(j, i) are false,
	// then the elements at index i and j are considered equal.
	// Sort may place equal elements in any order in the final result,
	// while Stable preserves the original input order of equal elements.
	//
	// Less must describe a transitive ordering:
	//  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
	//  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
	//
	// Note that floating-point comparison (the < operator on float32 or float64 values)
	// is not a transitive ordering when not-a-number (NaN) values are involved.
	// See Float64Slice.Less for a correct implementation for floating-point values.
	Less(i, j int) bool

	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h Interface) {
	// heapify
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if 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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

1
2
3
4
5
6

// 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)
}

1
2
3
4
5
6
7
8
9

// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to [Remove](h, 0).
func Pop(h Interface) any {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h Interface, i int) any {
	n := h.Len() - 1
	if n != i {
		h.Swap(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return h.Pop()
}

1
2
3
4
5
6
7
8
9

// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling [Remove](h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

package main

import (
	"container/heap"
	"fmt"
)

// MinHeap 定义小根堆类型
type MinHeap []int

// Len 实现 heap.Interface 接口的 Len 方法
func (h MinHeap) Len() int { return len(h) }

// Less 实现 heap.Interface 接口的 Less 方法（小根堆逻辑，大根堆使用 > ）
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }

// Swap 实现 heap.Interface 接口的 Swap 方法
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

// Push 实现 heap.Interface 接口的 Push 方法
func (h *MinHeap) Push(x any) {
	*h = append(*h, x.(int))
}

// Pop 实现 heap.Interface 接口的 Pop 方法
func (h *MinHeap) Pop() any {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[0 : n-1]
	return x
}

func main() {
	// 创建并初始化小根堆
	minHeap := &MinHeap{5, 2, 6, 3, 1, 4}

	heap.Init(minHeap)

	// 添加新元素
	heap.Push(minHeap, 0)
	heap.Push(minHeap, 7)

	// 弹出并打印最小值
	fmt.Println("Min element:", heap.Pop(minHeap)) // 0

	// 查看当前最小值（不弹出）
	fmt.Println("Current min:", (*minHeap)[0]) // 1

	// 遍历弹出所有元素
	fmt.Println("All elements in ascending order:")
	for minHeap.Len() > 0 {
		fmt.Print(heap.Pop(minHeap), " ") // 1, 2, 3, 4, 5, 6, 7
	}
}