ZBLOG

用 golang 写一个固定大小的最大堆的代码示例(堆中元素是不断填入的)

下面是一个使用Golang实现固定大小最大堆的代码示例:

  1. package main
  2. import (
  3. "container/heap"
  4. "fmt"
  5. )
  6. type MaxHeap struct {
  7. data []int
  8. length int
  9. }
  10. func (h *MaxHeap) Len() int { return h.length }
  11. func (h *MaxHeap) Less(i, j int) bool { return h.data[i] > h.data[j] }
  12. func (h *MaxHeap) Swap(i, j int) {
  13. h.data[i], h.data[j] = h.data[j], h.data[i]
  14. }
  15. func (h *MaxHeap) Push(x interface{}) {
  16. if len(h.data) < h.length {
  17. h.data = append(h.data, x.(int))
  18. } else if x.(int) > h.Peek() {
  19. heap.Pop(h)
  20. heap.Push(h, x)
  21. }
  22. }
  23. func (h *MaxHeap) Pop() interface{} {
  24. old := h.data
  25. n := len(old)
  26. x := old[n-1]
  27. h.data = old[0 : n-1]
  28. return x
  29. }
  30. func (h MaxHeap) Peek() int { return h.data[0] }
  31. func main() {
  32. // 创建一个大小为5的最大堆
  33. mh := &MaxHeap{make([]int, 0), 5}
  34. // 填充堆(这里只是简单地使用递增的数字)
  35. for i := 1; i <= 10; i++ {
  36. heap.Push(mh, i)
  37. fmt.Println("添加元素:", i)
  38. fmt.Println("当前堆中最大值:", mh.Peek())
  39. fmt.Println("当前堆中所有元素:", mh.data)
  40. fmt.Println()
  41. }
  42. }

该程序中使用了container/heap包来实现最大堆。我们定义了一个MaxHeap结构体,其中包含一个存储数据的切片和堆的大小。然后,我们实现了必需的方法:Len()Less()Swap()Push()Pop()。此外,我们还添加了一个辅助方法Peek()来返回最大值。

在主函数中,我们首先创建一个大小为5的最大堆,并使用递增数字填充它。每次添加元素时,我们都打印出当前堆中的最大值以及所有元素。

注意,在添加新元素时,如果堆已满,则只会将新元素添加到堆中(并未移除任何元素)。否则,我们会比较新元素与堆顶元素的大小,并在必要时弹出堆顶元素并将新元素推入堆中。这样可以确保堆始终保持固定大小,并且仅包含最大的几个元素。

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=4747

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?