heap.go

type KthLargest struct {
    k int
    items []int
}


func Constructor(k int, nums []int) KthLargest {
    this := KthLargest{k: k, items: make([]int, 0, k)}
    for _, num := range nums {
        this.Add(num)
    }
    return this
}


func (this *KthLargest) Add(val int) int {
    //minheap
    ix := len(this.items)
    this.items = append(this.items, val)
    for ix > 0 {
        if parentIx := (ix-1)/2; this.items[parentIx] > this.items[ix] {
            this.items[ix], this.items[parentIx] = this.items[parentIx], this.items[ix]
            ix = parentIx
            continue
        }
        break
    }
    for len(this.items) > this.k {
        this.Pop()
    }
    return this.items[0]
}

func (this *KthLargest) Pop() int {
    litems := len(this.items)
    if litems == 0 {
        return -1
    }
    this.items[0], this.items[litems-1] = this.items[litems-1], this.items[0]
    res := this.items[litems-1]
    this.items = this.items[:litems-1]
    litems--
    ix := 0
    for ix < litems {
        minIx := -1
        minItem := this.items[ix]
        if leftIx := 2 * ix + 1; leftIx < litems {
            if this.items[leftIx] < minItem {
                minIx = leftIx
                minItem = this.items[leftIx]
            }
        }
        if rightIx := 2 * ix + 2; rightIx < litems {
            if this.items[rightIx] < minItem {
                minIx = rightIx
                minItem = this.items[rightIx]
            }
        }
        if minIx == -1 {
            break
        }
        this.items[ix], this.items[minIx] = this.items[minIx], this.items[ix]
        ix = minIx
    }
    return res
}