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.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)