forked from akshitagit/JavaScript
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaxHeap.js
More file actions
99 lines (79 loc) · 2.42 KB
/
MaxHeap.js
File metadata and controls
99 lines (79 loc) · 2.42 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
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
/**
* In computer science, a min-max heap is a complete binary tree data structure
* which combines the usefulness of both a min-heap and a max-heap, that is,
* it provides constant time retrieval and logarithmic time removal of both
* the minimum and maximum elements in it.
* https://en.wikipedia.org/wiki/Min-max_heap
*/
class MaxHeap {
constructor() {
this.array = [];
}
peek() {
return this.array[0];
}
add(data) {
if (data === undefined) {
throw "data must be valid to add";
}
this.array.push(data);
this.bubbleUp(this.array.length - 1, data);
}
bubbleUp(childIndex, childData) {
if (childIndex > 0) {
const parentIndex = this.getParentIndex(childIndex);
const parentData = this.array[parentIndex];
if (this.shouldSwap(childData, parentData)) {
this.array[parentIndex] = childData;
this.array[childIndex] = parentData;
this.bubbleUp(parentIndex, childData);
}
}
}
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2);
}
removeHead() {
const headNode = this.array[0];
const tailNode = this.array.pop();
this.array[0] = tailNode;
this.bubbleDown(0, tailNode);
return headNode;
}
shouldSwap(childData, parentData) {
return childData > parentData;
}
bubbleDown(parentIndex, parentData) {
if (parentIndex < this.array.length) {
let targetIndex = parentIndex;
let targetData = parentData;
const leftChildIndex = this.getLeftChild(parentIndex);
const rightChildIndex = this.getRightChild(parentIndex);
if (leftChildIndex < this.array.length) {
const leftChildData = this.array[leftChildIndex];
if (this.shouldSwap(leftChildData, targetData)) {
targetIndex = leftChildIndex;
targetData = leftChildData;
}
}
if (rightChildIndex < this.array.length) {
const rightChildData = this.array[rightChildIndex];
if (this.shouldSwap(rightChildData, targetData)) {
targetIndex = rightChildIndex;
targetData = rightChildData;
}
}
if (targetIndex !== parentIndex) {
this.array[parentIndex] = targetData;
this.array[targetIndex] = parentData;
this.bubbleDown(targetIndex, parentData);
}
}
}
getLeftChild(parentIndex) {
return parentIndex * 2 + 1;
}
getRightChild(parentIndex) {
return parentIndex * 2 + 2;
}
}