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
}