-
Notifications
You must be signed in to change notification settings - Fork 0
/
Heap.js
106 lines (85 loc) · 2.44 KB
/
Heap.js
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
class Heap {
constructor(arr=[]){
this.heap = arr;
}
hasParent(index){
return this.heap[Math.floor((index - 1) / 2)]
}
hasLeftChild(index){
return this.heap[(index * 2) + 1]
}
hasRightChild(index){
return this.heap[(index * 2) + 2]
}
getParentIndex(index){
return Math.floor((index - 1) / 2)
}
getLeftChildIndex(index){
return (index * 2) + 1
}
getRightChildIndex(index){
return (index * 2) + 2
}
getParent(index){
return this.heap[Math.floor((index - 1) / 2)]
}
getLeftChild(index){
return this.heap[(index * 2) + 1]
}
getRightChild(index){
return this.heap[(index * 2) + 2]
}
peek(){
return this.heap[0]
}
add(element){
this.heap[this.heap.length] = element
this.#heapifyUp()
}
poll(){
let element = this.heap[0]
this.heap[0] = this.heap[this.heap.length - 1]
this.heap.length -=1
this.#heapifyDown()
return element
}
#heapifyUp(){
let index = this.heap.length - 1
while(this.hasParent(index) && this.getParent(index) > this.heap[index]){
[this.heap[this.getParentIndex(index)], this.heap[index]] =
[this.heap[index], this.heap[this.getParentIndex(index)]]
index = this.getParentIndex(index)
}
}
#heapifyDown(){
let index = 0, smallest = 0
while(this.hasLeftChild(index)){
smallest = this.getLeftChildIndex(index);
if(this.hasRightChild(index) && this.getRightChild(index) < this.getLeftChild(smallest)){
smallest = this.getRightChildIndex(index)
}
if(this.heap[index] < this.heap[smallest]) return
else {
[this.heap[smallest], this.heap[index]] =
[this.heap[index], this.heap[smallest]]
index = smallest
}
}
}
findTheHighestKthElement(k){
let highest = [this.poll()]
while(k-1){
highest = [...highest, this.poll()]
k--;
}
return highest
}
}
let heap = new Heap([]);
console.log('add 100 ', heap.add(100))
console.log('add 10 ', heap.add(10))
console.log('add 9', heap.add(9))
// console.log('poll ', heap.poll())
console.log('add 1 ', heap.add(1))
console.log('highest', heap.findTheHighestKthElement(3))
console.log(heap)