Go自定义PriorityQueue优先队列使用Heap堆

2023-12-23 23:30:13

题目

在这里插入图片描述

分析

每次找最大的,pop出来
然后折半,再丢进去

go写法

go如果想用heap,要实现less\len\swap\push\pop
但可以偷懒,用sort.IntSlice,已经实现了less\len\swap
但由于目前是大根堆,要重写一下less
因此,优先队列的自定义则为

// heap对应的interface要实现less\len\swap\push\pop
// 但intslice已经实现less\len\swap,但less要重写
type PriorityQueue struct {
    sort.IntSlice
}

func(pq *PriorityQueue) Less(i, j int) bool {
    return pq.IntSlice[i] > pq.IntSlice[j] // 大根堆
}

func(pq *PriorityQueue) Push(v interface{}) {
    pq.IntSlice = append(pq.IntSlice, v.(int)) // interface转int
}

func (pq *PriorityQueue) Pop() interface{} {
    arr := pq.IntSlice
    v := arr[len(arr) - 1]
    pq.IntSlice = arr[:len(arr) - 1]
    return v
}

ac code

// heap对应的interface要实现less\len\swap\push\pop
// 但intslice已经实现less\len\swap,但less要重写
type PriorityQueue struct {
    sort.IntSlice
}

func(pq *PriorityQueue) Less(i, j int) bool {
    return pq.IntSlice[i] > pq.IntSlice[j] // 大根堆
}

func(pq *PriorityQueue) Push(v interface{}) {
    pq.IntSlice = append(pq.IntSlice, v.(int)) // interface转int
}

func (pq *PriorityQueue) Pop() interface{} {
    arr := pq.IntSlice
    v := arr[len(arr) - 1]
    pq.IntSlice = arr[:len(arr) - 1]
    return v
}


func minStoneSum(piles []int, k int) int {
    pq := &PriorityQueue{piles} // 传引用,方便修改
    heap.Init(pq)
    for i := 0; i < k; i++ {
        pile := heap.Pop(pq).(int)
        pile -= pile / 2
        heap.Push(pq, pile)
    }
    sum := 0
    for len(pq.IntSlice) > 0 {
        sum += heap.Pop(pq).(int)
    }
    return sum
}

总结

注意pq自定义的时候要传引用,这样才能完成修改,而并非复制
注意interface()和基本数据类型的转换.(int)

文章来源:https://blog.csdn.net/weixin_40986490/article/details/135165733
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。