ZBLOG

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

下面是一个使用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的最大堆,并使用递增数字填充它。每次添加元素时,我们都打印出当前堆中的最大值以及所有元素。

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

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

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

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

联系我们

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

微信号:3007537140

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

关注我们
x

注册

已经有帐号?