Skip to content

Commit 9c6e44e

Browse files
Abdullah03096344305Abdullah03096344305
committed
Improved the Heap.js File by adding more comments and increase deep understanding.
1 parent 405279c commit 9c6e44e

File tree

1 file changed

+110
-91
lines changed

1 file changed

+110
-91
lines changed

‎src/data-structures/heap.js

Lines changed: 110 additions & 91 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,22 @@
11
/**
2-
* A binary heap is a complete binary tree which
3-
* satisfies the heap ordering property.
2+
* A binary heap is a complete binary tree that satisfies the heap ordering property.
3+
* This implementation supports both minimum and maximum heaps, depending on the
4+
* comparison function provided. If no comparison function is provided, it defaults to
5+
* a minimum heap.
46
*
57
* @example
68
* var Heap = require('path-to-algorithms/src/data-structures/heap').Heap;
79
*
10+
* // Example for a max heap using birthyear for comparison:
811
* var heap = new Heap(function(a, b) {
912
* return a.birthyear - b.birthyear;
1013
* });
1114
*
12-
* heap.add({
13-
* name: 'John',
14-
* birthyear: 1981
15-
* });
16-
* heap.add({
17-
* name: 'Pavlo',
18-
* birthyear: 2000
19-
* });
20-
* heap.add({
21-
* name: 'Garry',
22-
* birthyear: 1989
23-
* });
24-
* heap.add({
25-
* name: 'Derek',
26-
* birthyear: 1990
27-
* });
28-
* heap.add({
29-
* name: 'Ivan',
30-
* birthyear: 1966
31-
* });
15+
* heap.add({ name: 'John', birthyear: 1981 });
16+
* heap.add({ name: 'Pavlo', birthyear: 2000 });
17+
* heap.add({ name: 'Garry', birthyear: 1989 });
18+
* heap.add({ name: 'Derek', birthyear: 1990 });
19+
* heap.add({ name: 'Ivan', birthyear: 1966 });
3220
*
3321
* console.log(heap.extract()); // { name: 'Pavlo', birthyear: 2000 }
3422
* console.log(heap.extract()); // { name: 'Derek', birthyear: 1990 }
@@ -39,96 +27,111 @@
3927
* @module data-structures/heap
4028
*/
4129
(function (exports) {
42-
43-
'use strict';
30+
"use strict";
4431

4532
/**
46-
* Minimum heap constructor.
33+
* Heap constructor.
34+
* The heap can be either a min-heap or max-heap, determined by the comparison function.
35+
* By default, it behaves as a min-heap if no comparison function is provided.
4736
*
4837
* @public
4938
* @constructor
50-
* @param {Function} cmp Function used for comparison between the elements.
39+
* @param {Function} cmp A function used for comparing elements (optional).
40+
* It should return a positive number if a > b,
41+
* a negative number if a < b, and 0 if they are equal.
5142
*/
5243
exports.Heap = function (cmp) {
5344
this._heap = [];
54-
if (typeof cmp === 'function') {
55-
this._cmp = cmp;
56-
} else {
57-
this._cmp = function (a, b) {
58-
return a - b;
59-
};
60-
}
45+
// If comparison function is provided, use it; otherwise, use default for min-heap.
46+
this._cmp =
47+
typeof cmp === "function"
48+
? cmp
49+
: function (a, b) {
50+
return a - b;
51+
};
6152
};
6253

6354
/**
64-
* Exchange indexes with start index given as argument
65-
* to turn the tree into a valid heap. On a single call
66-
* this method maintains only a single "branch" of the heap.<br><br>
55+
* Heapifies the subtree rooted at the given index, maintaining the heap property.
56+
* This method assumes that the subtrees are already valid heaps and fixes the
57+
* heap rooted at the provided index.
6758
*
6859
* Time complexity: O(log N).
6960
*
7061
* @private
71-
* @param {Number} index The parent.
62+
* @param {Number} index Index of the node to heapify.
7263
*/
7364
exports.Heap.prototype._heapify = function (index) {
74-
var extr = index;
75-
var left = 2 * index + 1;
76-
var right = 2 * index + 2;
65+
var largest = index;
66+
var left = 2 * index + 1; // Left child index
67+
var right = 2 * index + 2; // Right child index
7768
var temp;
7869

79-
if (left < this._heap.length &&
80-
this._cmp(this._heap[left], this._heap[index]) > 0) {
81-
extr = left;
70+
// Compare the left child with the current node (index).
71+
if (
72+
left < this._heap.length &&
73+
this._cmp(this._heap[left], this._heap[index]) > 0
74+
) {
75+
largest = left;
8276
}
8377

84-
if (right < this._heap.length &&
85-
this._cmp(this._heap[right], this._heap[index]) > 0 &&
86-
this._cmp(this._heap[right], this._heap[left]) > 0) {
87-
extr = right;
78+
// Compare the right child with the current largest node.
79+
if (
80+
right < this._heap.length &&
81+
this._cmp(this._heap[right], this._heap[largest]) > 0
82+
) {
83+
largest = right;
8884
}
8985

90-
if (index !== extr) {
86+
// If the largest node is not the current index, swap and heapify.
87+
if (largest !== index) {
9188
temp = this._heap[index];
92-
this._heap[index] = this._heap[extr];
93-
this._heap[extr] = temp;
94-
this._heapify(extr);
89+
this._heap[index] = this._heap[largest];
90+
this._heap[largest] = temp;
91+
// Recursively heapify the affected subtree.
92+
this._heapify(largest);
9593
}
9694
};
9795

9896
/**
99-
* Changes the key.<br><br>
100-
* Complexity: O(log N).
97+
* Changes the key/value of the element at the given index and repositions it
98+
* to maintain the heap property.
99+
*
100+
* Time complexity: O(log N).
101101
*
102102
* @public
103-
* @param {Number} index Index of the value which should be changed.
104-
* @param {Number|Object} value New value according to the index.
105-
* @return {Number} New position of the element.
103+
* @param {Number} index Index of the element to change.
104+
* @param {Number|Object} value The new value for the element.
105+
* @return {Number} The new position of the element.
106106
*/
107107
exports.Heap.prototype.changeKey = function (index, value) {
108108
this._heap[index] = value;
109109
var elem = this._heap[index];
110-
var parent = Math.floor(index / 2);
110+
var parent = Math.floor((index - 1) / 2); // Parent index (use (index-1)/2 for zero-based index).
111111
var temp;
112-
if (elem !== undefined) {
113-
while (parent >= 0 && this._cmp(elem, this._heap[parent]) > 0) {
114-
temp = this._heap[parent];
115-
this._heap[parent] = elem;
116-
this._heap[index] = temp;
117-
index = parent;
118-
parent = Math.floor(parent / 2);
119-
}
120-
this._heapify(index);
112+
113+
// Move the element up the tree if it's greater than its parent.
114+
while (index > 0 && this._cmp(elem, this._heap[parent]) > 0) {
115+
temp = this._heap[parent];
116+
this._heap[parent] = elem;
117+
this._heap[index] = temp;
118+
index = parent;
119+
parent = Math.floor((parent - 1) / 2);
121120
}
122-
return parent;
121+
122+
// Ensure the heap is valid after key change.
123+
this._heapify(index);
124+
return index;
123125
};
124126

125127
/**
126-
* Updates a given node. This operation is useful
127-
* in algorithms like Dijkstra, A* where we need
128-
* to decrease/increase value of the given node.
128+
* Updates a specific node by repositioning it in the heap to maintain the heap property.
129+
* This is useful in algorithms where node values need to be updated, such as Dijkstra's or A*.
130+
*
131+
* Time complexity: O(log N).
129132
*
130133
* @public
131-
* @param {Number|Object} node Node which should be updated.
134+
* @param {Number|Object} node The node to be updated.
132135
*/
133136
exports.Heap.prototype.update = function (node) {
134137
var idx = this._heap.indexOf(node);
@@ -138,58 +141,74 @@
138141
};
139142

140143
/**
141-
* Adds new element to the heap.<br><br>
142-
* Complexity: O(log N).
144+
* Adds a new element to the heap, maintaining the heap property.
145+
*
146+
* Time complexity: O(log N).
143147
*
144148
* @public
145-
* @param {Number|Object} value Value which will be inserted.
146-
* @return {Number} Index of the inserted value.
149+
* @param {Number|Object} value The value to be added to the heap.
150+
* @return {Number} The index of the inserted value.
147151
*/
148152
exports.Heap.prototype.add = function (value) {
153+
// Insert the value at the end of the array and then move it to the correct position.
149154
this._heap.push(value);
150155
return this.changeKey(this._heap.length - 1, value);
151156
};
152157

153158
/**
154-
* Returns current value which is on the top of the heap.<br><br>
155-
* Complexity: O(1).
159+
* Retrieves, but does not remove, the element at the top of the heap (the extremum).
160+
*
161+
* Time complexity: O(1).
156162
*
157163
* @public
158-
* @return {Number|Object} Current top value.
164+
* @return {Number|Object} The current top value of the heap.
159165
*/
160166
exports.Heap.prototype.top = function () {
161167
return this._heap[0];
162168
};
163169

164170
/**
165-
* Removes and returns the current extremum value
166-
* which is on the top of the heap.<br><br>
167-
* Complexity: O(log N).
171+
* Removes and returns the top (extremum) element from the heap.
172+
* After removal, the heap property is restored.
173+
*
174+
* Time complexity: O(log N).
168175
*
169176
* @public
170-
* @returns {Number|Object} The extremum value.
177+
* @return {Number|Object} The extremum value removed from the heap.
178+
* @throws Will throw an error if the heap is empty.
171179
*/
172180
exports.Heap.prototype.extract = function () {
173-
if (!this._heap.length) {
174-
throw 'The heap is already empty!';
181+
if (this._heap.length === 0) {
182+
throw new Error("The heap is already empty!");
183+
}
184+
185+
// Swap the top element with the last one, remove the last, and heapify the top.
186+
var extr = this._heap[0];
187+
var last = this._heap.pop();
188+
if (this._heap.length > 0) {
189+
this._heap[0] = last;
190+
this._heapify(0);
175191
}
176-
var extr = this._heap.shift();
177-
this._heapify(0);
178192
return extr;
179193
};
180194

195+
/**
196+
* Returns the entire collection of the heap's elements.
197+
*
198+
* @public
199+
* @return {Array} An array representing the heap's internal collection.
200+
*/
181201
exports.Heap.prototype.getCollection = function () {
182202
return this._heap;
183203
};
184204

185205
/**
186-
* Checks or heap is empty.
206+
* Checks if the heap is empty.
187207
*
188208
* @public
189-
* @returns {Boolean} Returns true if heap is empty.
209+
* @return {Boolean} True if the heap is empty, otherwise false.
190210
*/
191211
exports.Heap.prototype.isEmpty = function () {
192-
return !this._heap.length;
212+
return this._heap.length === 0;
193213
};
194-
195-
})(typeof window === 'undefined' ? module.exports : window);
214+
})(typeof window === "undefined" ? module.exports : window);

0 commit comments

Comments
 (0)