题解 | #寻找第K大#

package main

func findKth(a []int, n int, K int) int {
	K = n - K + 1
	var heap []int
	heap = append(heap,0)
	for i := 0; i < K; i++ {
		heap = add(heap, a[i])
	}
	for i := K; i < n; i++ {
		if heap[1] > a[i] {
			heap[1] = a[i]
			down(heap, 1)
		}
	}
	return heap[1]
}

func down(heap []int, idx int) {
	le := len(heap)
	for idx < le {
		next := idx
		left := idx << 1
		if left < le && heap[left] > heap[next] {
			next = left
		}
		right := left + 1
		if right < le && heap[right] > heap[next] {
			next = right
		}
		if idx != next {
			tmp := heap[idx]
			heap[idx] = heap[next]
			heap[next] = tmp
			idx = next
		} else {
			break
		}
	}
}

func add(heap []int, val int) []int {
	heap = append(heap, val)
	idx := len(heap) - 1
	up(heap, idx)
	return heap
}

func up(heap []int, idx int) {
	for idx > 1 {
		parent := idx >> 1
		if heap[parent] >= heap[idx] {
			break
		}
		tmp := heap[parent]
		heap[parent] = heap[idx]
		heap[idx] = tmp
		idx = parent
	}
}