-
Notifications
You must be signed in to change notification settings - Fork 1
/
ds.js
66 lines (57 loc) · 1.65 KB
/
ds.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
class PowerOfTwoMaxHeap {
constructor(x) {
this.x = x;
this.heap = [];
}
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
}
popMax() {
if (this.heap.length === 0) return null;
const max = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown(0);
}
return max;
}
bubbleUp(index) {
const parentIndex = this.getParentIndex(index);
if (index > 0 && this.heap[index] > this.heap[parentIndex]) {
this.swap(index, parentIndex);
this.bubbleUp(parentIndex);
}
}
sinkDown(index) {
const leftChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
let maxChildIndex = null;
if (leftChildIndex < this.heap.length) {
maxChildIndex = leftChildIndex;
}
if (rightChildIndex < this.heap.length &&
this.heap[rightChildIndex] > this.heap[leftChildIndex]) {
maxChildIndex = rightChildIndex;
}
if (maxChildIndex !== null && this.heap[index] < this.heap[maxChildIndex]) {
this.swap(index, maxChildIndex);
this.sinkDown(maxChildIndex);
}
}
getParentIndex(index) {
return Math.floor((index - 1) / this.x);
}
getLeftChildIndex(index) {
return index * this.x + 1;
}
getRightChildIndex(index) {
return index * this.x + this.x + 1;
}
swap(index1, index2) {
const temp = this.heap[index1];
this.heap[index1] = this.heap[index2];
this.heap[index2] = temp;
}
}