-
Notifications
You must be signed in to change notification settings - Fork 0
/
Heaps2.js
110 lines (86 loc) · 2.23 KB
/
Heaps2.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
107
108
109
110
/** Tree-based partially ordered data structure
* Two types : max-heap and min-heap
* Any node's key <= parent's key >= child's keys
*/
/** Binary Heap
* a complete binary tree
* effective for implementing a priority queue
* implemented as an array
*/
/** Complexity
* Push : O(log n)
* Poll : O(log n)
* Search : O(n)
* Peek : O(1)
*/
/** reference : https://www.youtube.com/watch?v=hzxa4psfxxg&ab_channel=QuestionableCoding */
class Heap {
constructor() {
this.data = [];
}
getParentIndex(i) {
return Math.floor((i - 1) / 2);
}
getLeftChildIndex(i) {
return i * 2 + 1;
}
getRightChildIndex(i) {
return i * 2 + 2;
}
swap(i1, i2) {
const temp = this.data[i1];
this.data[i1] = this.data[i2];
this.data[i2] = temp;
}
push(key) {
this.data[this.data.length] = key;
this.heapifyUp();
}
heapifyUp() {
let current = this.data.length - 1;
while (this.data[current] > this.data[this.getParentIndex(current)]) {
this.swap(current, this.getParentIndex(current));
current = this.getParentIndex(current);
}
}
poll() {
const maxValue = this.data[0];
this.data[0] = this.data[this.data.length - 1];
this.data.length--;
this.heapifyDown();
return maxValue;
}
heapifyDown() {
let current = 0;
while (this.data[this.getLeftChildIndex(current)] !== undefined) {
let biggestChildidx = this.getLeftChildIndex(current);
if (this.data[this.getRightChildIndex(current)] !== undefined &&
this.data[this.getRightChildIndex(current)] > this.data[this.getLeftChildIndex(current)]) {
biggestChildidx = this.getRightChildIndex(current);
}
}
if (this.data[current] < this.data[biggestChildidx]) {
this.swap(current, biggestChildidx);
current = biggestChildidx;
} else {
return ;
}
}
}
const heap = new Heap();
console.log(heap);
heap.push(25);
heap.push(5);
heap.push(40);
heap.push(70);
heap.push(90);
heap.push(44);
console.log(heap.data.join(','));
let a = [];
a.push(heap.poll());
a.push(heap.poll());
a.push(heap.poll());
a.push(heap.poll());
a.push(heap.poll());
console.log('Top 5 items:', a);
console.log(heap.data.join(','));