gistfile1.txt

type KthLargest struct {
	n []int
	l int
}


func Constructor(k int, nums []int) KthLargest {
	r :=  KthLargest{n:make([]int,k)}

	for _, n := range nums {
		r.Add(n)
	}
	return r
}


func (this *KthLargest) add(val int) {
	this.n[this.l] = val

	this.l += 1

	if this.l == 1 {
		return
	}

	ci := this.l - 1

	for ci != 0 {
		pi := ( ci - 1 ) / 2

		if this.n[pi] < this.n[ci] {
			break
		}

		this.n[pi] , this.n[ci] = this.n[ci] , this.n[pi]
		ci = pi
	}

	return
}

func (this *KthLargest) peek(v int) {
	ci := 0
	this.n[0] = v

	for ci < this.l {
		li := ( ci + 1 ) * 2 - 1
		ri := ( ci + 1 ) * 2

		if li >= this.l {
			break
		}

		if ri >= this.l {
			if this.n[ci] > this.n[li] {
				this.swap(ci,li)
				ci = li
				continue
			}
			break
		}

		if this.n[ri] < this.n[ci] {
			if this.n[ri] > this.n[li] {
				this.swap(ci,li)
				ci = li
				continue
			}
			this.swap(ci,ri)
			ci = ri
			continue
		}

		if this.n[li] < this.n[ci] {
			this.swap(ci,li)
			ci = li
			continue
		}

		break
	}

}

func (this *KthLargest) Add(val int) int {
	if this.l == len(this.n) {
		if this.n[0] > val {
			return this.n[0]
		}

		this.peek(val)
		return this.n[0]

	}

	this.add(val)
	return this.n[0]
}

func (this *KthLargest) swap(ci int, li int) {
	this.n[ci],this.n[li] = this.n[li],this.n[ci]
}