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

题目

在这里插入图片描述

分析

每次找最大的，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.IntSlicev := 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.IntSlicev := 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 / 2heap.Push(pq, pile)}sum := 0for len(pq.IntSlice) > 0 {sum += heap.Pop(pq).(int)}return sum
}