-
Notifications
You must be signed in to change notification settings - Fork 236
/
binaryHeap.js
86 lines (77 loc) · 2.34 KB
/
binaryHeap.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
function getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2);
}
function getLeftChild(parentIndex) {
return (parentIndex * 2) + 1;
}
function getRightChild(parentIndex) {
return (parentIndex * 2) + 2;
}
class BinaryHeap {
constructor(data = []) {
this.array = [];
if (data && Array.isArray(data)) {
this.array = data;
const { length } = this.array;
for (let i = Math.floor((length - 1) / 2); i >= 0; i--) {
this.bubbleDown(i, this.array[i]);
}
}
}
add(data) {
if (data === undefined) {
throw new Error('data must be valid to add');
}
this.array.push(data);
this.bubbleUp(this.array.length - 1, data);
}
removeHead() {
const headNode = this.array[0];
const tailNode = this.array.pop();
if (this.array.length) {
this.array[0] = tailNode;
this.bubbleDown(0, tailNode);
}
return headNode;
}
bubbleDown(parentIndex, parentData) {
if (parentIndex < this.array.length) {
let targetIndex = parentIndex;
let targetData = parentData;
const leftChildIndex = getLeftChild(parentIndex);
const rightChildIndex = getRightChild(parentIndex);
const trySwap = (index, array, shouldSwap) => {
if (index < array.length) {
const data = array[index];
if (shouldSwap(data, targetData)) {
targetIndex = index;
targetData = data;
}
}
};
trySwap(leftChildIndex, this.array, this.shouldSwap);
trySwap(rightChildIndex, this.array, this.shouldSwap);
if (targetIndex !== parentIndex) {
this.array[parentIndex] = targetData;
this.array[targetIndex] = parentData;
this.bubbleDown(targetIndex, parentData);
}
}
}
bubbleUp(childIndex, childData) {
if (childIndex > 0) {
const parentIndex = getParentIndex(childIndex);
const parentData = this.array[parentIndex];
if (this.shouldSwap(childData, parentData)) {
this.array[parentIndex] = childData;
this.array[childIndex] = parentData;
this.bubbleUp(parentIndex, childData);
}
}
}
// eslint-disable-next-line class-methods-use-this
shouldSwap() {
throw new Error('This method is not implemented. Concrete implementations should implement.');
}
}
module.exports = { BinaryHeap, getLeftChild, getRightChild };