-
Notifications
You must be signed in to change notification settings - Fork 1
/
215.KthLargestElementInAnArray.go
55 lines (51 loc) · 1.26 KB
/
215.KthLargestElementInAnArray.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func findKthLargest(nums []int, k int) int {
minheap := nums[:k]
Heapify(minheap, false)
for i := k;i < len(nums);i++{
if nums[i] >= minheap[0]{
minheap[0] = nums[i]
percolateDown(minheap, 0, IsMaxHeap(false))
}
}
return minheap[0]
}
func Heapify(src []int, ismax bool) {
i := (len(src) - 1) / 2
hc := IsMaxHeap(ismax)
for ; i >= 0; i-- {
percolateDown(src, i, hc)
}
}
func IsMaxHeap(isMax bool) func(int, int) bool {
return func(a int, b int) bool{
if isMax {
return a > b
}else{
return a < b
}
}
}
func percolateDown(src []int, parentIdx int, comper func(int, int) bool) {
leftChildIdx := parentIdx*2 + 1
rightChildIdx := (parentIdx + 1) * 2
var percolateChildIdx int
if (leftChildIdx <= len(src)-1) && (rightChildIdx <= len(src)-1) {
if comper(src[leftChildIdx], src[rightChildIdx]) {
percolateChildIdx = leftChildIdx
} else {
percolateChildIdx = rightChildIdx
}
} else if leftChildIdx <= len(src)-1 {
percolateChildIdx = leftChildIdx
} else if rightChildIdx <= len(src)-1 {
percolateChildIdx = rightChildIdx
} else {
return
}
if comper(src[percolateChildIdx], src[parentIdx]) {
t := src[percolateChildIdx]
src[percolateChildIdx] = src[parentIdx]
src[parentIdx] = t
percolateDown(src, percolateChildIdx, comper)
}
}