堆相关知识点

堆类题目堆相关知识点

golang 最小堆实现

https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/submissions/

参考 https://ieevee.com/tech/2018/01/29/go-heap.html#2-containerheap%E6%8F%90%E4%BE%9B%E7%9A%84%E6%96%B9%E6%B3%95

container/heap

4.1 heap.Init

4.2 heap.Push

4.3 heap.Pop

4.4 heap.Fix

4.5 heap.Remove

实现

type KthLargest struct {
    sort.IntSlice
}
// IntSlice类型替我们实现了
/*
func (h KthLargest) Len() int           { return len(h) }
func (h KthLargest) Less(i, j int) bool { return h[i] < h[j] }
func (h KthLargest) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
*/


// add x as element Len()
func (kl *KthLargest) Push(v interface{}) {
    kl.IntSlice = append(kl.IntSlice, v.(int))
}

// !!注意此处Pop的实现，由于golang heap库在调用heap.Pop方法时，先把元素和最后一个节点的值交换，然后弹出，然后调用 down。因此我们自己实现的方法接收到Pop时，需要被pop的元素实际已经被放置到队尾了
// remove and return element Len() - 1
func (kl *KthLargest) Pop() interface{} {
    a := kl.IntSlice
    v := a[len(a)-1]
    kl.IntSlice = a[:len(a)-1]
    return v
}


// heap.Push(kl, val)
// val = heap.Pop(kl)