下面是一个使用Golang实现固定大小最大堆的代码示例:
package main
import (
"container/heap"
"fmt"
)
type MaxHeap struct {
data []int
length int
}
func (h *MaxHeap) Len() int { return h.length }
func (h *MaxHeap) Less(i, j int) bool { return h.data[i] > h.data[j] }
func (h *MaxHeap) Swap(i, j int) {
h.data[i], h.data[j] = h.data[j], h.data[i]
}
func (h *MaxHeap) Push(x interface{}) {
if len(h.data) < h.length {
h.data = append(h.data, x.(int))
} else if x.(int) > h.Peek() {
heap.Pop(h)
heap.Push(h, x)
}
}
func (h *MaxHeap) Pop() interface{} {
old := h.data
n := len(old)
x := old[n-1]
h.data = old[0 : n-1]
return x
}
func (h MaxHeap) Peek() int { return h.data[0] }
func main() {
// 创建一个大小为5的最大堆
mh := &MaxHeap{make([]int, 0), 5}
// 填充堆(这里只是简单地使用递增的数字)
for i := 1; i <= 10; i++ {
heap.Push(mh, i)
fmt.Println("添加元素:", i)
fmt.Println("当前堆中最大值:", mh.Peek())
fmt.Println("当前堆中所有元素:", mh.data)
fmt.Println()
}
}
该程序中使用了container/heap
包来实现最大堆。我们定义了一个MaxHeap
结构体,其中包含一个存储数据的切片和堆的大小。然后,我们实现了必需的方法:Len()
、Less()
、Swap()
、Push()
和Pop()
。此外,我们还添加了一个辅助方法Peek()
来返回最大值。
在主函数中,我们首先创建一个大小为5的最大堆,并使用递增数字填充它。每次添加元素时,我们都打印出当前堆中的最大值以及所有元素。
注意,在添加新元素时,如果堆已满,则只会将新元素添加到堆中(并未移除任何元素)。否则,我们会比较新元素与堆顶元素的大小,并在必要时弹出堆顶元素并将新元素推入堆中。这样可以确保堆始终保持固定大小,并且仅包含最大的几个元素。