JavaScript/Data-Structures/Heap/BinaryHeap.js at master · sibalonecoding-code/JavaScript · GitHub

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/**
 * BinaryHeap class represents a binary heap data structure that can be configured as a Min Heap or Max Heap.
 *
 * Binary heaps are binary trees that are filled level by level and from left to right inside each level.
 * They have the property that any parent node has a smaller (for Min Heap) or greater (for Max Heap) priority
 * than its children, ensuring that the root of the tree always holds the extremal value.
 */
classBinaryHeap{
/**
 * Creates a new BinaryHeap instance.
 * @constructor
 * @param {Function} comparatorFunction - The comparator function used to determine the order of elements (e.g., minHeapComparator or maxHeapComparator).
 */
constructor(comparatorFunction){
/**
 * The heap array that stores elements.
 * @member {Array}
 */
this.heap=[]

/**
 * The comparator function used for ordering elements in the heap.
 * @member {Function}
 */
this.comparator=comparatorFunction
}

/**
 * Inserts a new value into the heap.
 * @param {*} value - The value to be inserted into the heap.
 */
insert(value){
this.heap.push(value)
this.#bubbleUp(this.heap.length-1)
}

/**
 * Returns the number of elements in the heap.
 * @returns {number} - The number of elements in the heap.
 */
size(){
returnthis.heap.length
}

/**
 * Checks if the heap is empty.
 * @returns {boolean} - True if the heap is empty, false otherwise.
 */
empty(){
returnthis.size()===0
}

/**
 * Bubbles up a value from the specified index to maintain the heap property.
 * @param {number} currIdx - The index of the value to be bubbled up.
 * @private
 */
 #bubbleUp(currIdx){
letparentIdx=Math.floor((currIdx-1)/2)

while(
currIdx>0&&
this.comparator(this.heap[currIdx],this.heap[parentIdx])
){
this.#swap(currIdx,parentIdx)
currIdx=parentIdx
parentIdx=Math.floor((currIdx-1)/2)
}
}

/**
 * Sinks down a value from the specified index to maintain the heap property.
 * @param {number} currIdx - The index of the value to be sunk down.
 * @private
 */
 #sinkDown(currIdx){
letchildOneIdx=currIdx*2+1

while(childOneIdx<this.size()){
constchildTwoIdx=childOneIdx+1<this.size() ? childOneIdx+1 : -1
constswapIdx=
childTwoIdx!==-1&&
this.comparator(this.heap[childTwoIdx],this.heap[childOneIdx])
 ? childTwoIdx
 : childOneIdx

if(this.comparator(this.heap[swapIdx],this.heap[currIdx])){
this.#swap(currIdx,swapIdx)
currIdx=swapIdx
childOneIdx=currIdx*2+1
}else{
return
}
}
}

/**
 * Retrieves the top element of the heap without removing it.
 * @returns {*} - The top element of the heap.
 */
peek(){
returnthis.heap[0]
}

/**
 * Removes and returns the top element of the heap.
 * @returns {*} - The top element of the heap.
 */
extractTop(){
consttop=this.peek()
constlast=this.heap.pop()

if(!this.empty()){
this.heap[0]=last
this.#sinkDown(0)
}

returntop
}

/**
 * Swaps elements at two specified indices in the heap.
 * @param {number} index1 - The index of the first element to be swapped.
 * @param {number} index2 - The index of the second element to be swapped.
 * @private
 */
 #swap(index1,index2){
;[this.heap[index1],this.heap[index2]]=[
this.heap[index2],
this.heap[index1]
]
}
}

/**
 * Comparator function for creating a Min Heap.
 * @param {*} a - The first element to compare.
 * @param {*} b - The second element to compare.
 * @returns {boolean} - True if 'a' should have higher priority than 'b' in the Min Heap, false otherwise.
 */
constminHeapComparator=(a,b)=>a<b

/**
 * Comparator function for creating a Max Heap.
 * @param {*} a - The first element to compare.
 * @param {*} b - The second element to compare.
 * @returns {boolean} - True if 'a' should have higher priority than 'b' in the Max Heap, false otherwise.
 */
constmaxHeapComparator=(a,b)=>a>b

export{BinaryHeap,minHeapComparator,maxHeapComparator}