Repository navigation
Expand file tree
/
Copy pathmin_heap_construction.js
More file actions
64 lines (57 loc) · 1.5 KB
/
Copy pathmin_heap_construction.js
File metadata and controls
64 lines (57 loc) · 1.5 KB
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
class MinHeap {
constructor(array) {
this.heap = this.buildHeap(array);
}
buildHeap(array) {
const parIdx = Math.floor((array.length - 2) / 2);
for (let idx = parIdx; idx >= 0; idx--) {
this.siftDown(idx, array.length - 1, array);
}
return array;
}
siftDown(curIdx, endIdx, heap) {
let firstChildIdx = curIdx * 2 + 1;
while (firstChildIdx <= endIdx) {
let secondChildIdx = curIdx * 2 + 2 <= endIdx ? curIdx * 2 + 2 : -1;
let idxSwap;
if (secondChildIdx !== -1 && heap[secondChildIdx] < heap[firstChildIdx]) {
idxSwap = secondChildIdx;
} else {
idxSwap = firstChildIdx;
}
if (heap[idxSwap] < heap[curIdx]) {
this.swap(idxSwap, curIdx, heap);
curIdx = idxSwap;
firstChildIdx = curIdx * 2 + 1;
} else {
return;
}
}
}
siftUp(curIdx, heap) {
let parIdx = Math.floor((curIdx - 1) / 2);
while (parIdx >= 0 && heap[parIdx] > heap[curIdx]) {
this.swap(parIdx, curIdx, heap);
curIdx = parIdx;
parIdx = Math.floor((curIdx - 1) / 2);
}
}
remove() {
this.swap(0, this.heap.length - 1, this.heap);
const valToRemove = this.heap.pop();
this.siftDown(0, this.heap.length - 1, this.heap);
return valToRemove;
}
insert(value) {
this.heap.push(value);
this.siftUp(this.heap.length - 1, this.heap);
}
peek() {
return this.heap[0];
}
swap(i, j, heap) {
const temp = heap[j];
heap[j] = heap[i];
heap[i] = temp;
}
}