data-structures/heap.js

  1. /**
  2. * A binary heap is a complete binary tree which
  3. * satisfies the heap ordering property.
  4. *
  5. * @example
  6. * var Heap = require('path-to-algorithms/src/data-structures/heap').Heap;
  7. *
  8. * var heap = new Heap(function(a, b) {
  9. * return a.birthyear - b.birthyear;
  10. * });
  11. *
  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. * });
  32. *
  33. * console.log(heap.extract()); // { name: 'Pavlo', birthyear: 2000 }
  34. * console.log(heap.extract()); // { name: 'Derek', birthyear: 1990 }
  35. * console.log(heap.extract()); // { name: 'Garry', birthyear: 1989 }
  36. * console.log(heap.extract()); // { name: 'John', birthyear: 1981 }
  37. * console.log(heap.extract()); // { name: 'Ivan', birthyear: 1966 }
  38. *
  39. * @module data-structures/heap
  40. */
  41. (function (exports) {
  42. 'use strict';
  43. /**
  44. * Minimum heap constructor.
  45. *
  46. * @public
  47. * @constructor
  48. * @param {Function} cmp Function used for comparison between the elements.
  49. */
  50. exports.Heap = function (cmp) {
  51. this._heap = [];
  52. if (typeof cmp === 'function') {
  53. this._cmp = cmp;
  54. } else {
  55. this._cmp = function (a, b) {
  56. return a - b;
  57. };
  58. }
  59. };
  60. /**
  61. * Exchange indexes with start index given as argument
  62. * to turn the tree into a valid heap. On a single call
  63. * this method maintains only a single "branch" of the heap.<br><br>
  64. *
  65. * Time complexity: O(log N).
  66. *
  67. * @private
  68. * @param {Number} index The parent.
  69. */
  70. exports.Heap.prototype._heapify = function (index) {
  71. var extr = index;
  72. var left = 2 * index + 1;
  73. var right = 2 * index + 2;
  74. var temp;
  75. if (left < this._heap.length &&
  76. this._cmp(this._heap[left], this._heap[index]) > 0) {
  77. extr = left;
  78. }
  79. if (right < this._heap.length &&
  80. this._cmp(this._heap[right], this._heap[index]) > 0 &&
  81. this._cmp(this._heap[right], this._heap[left]) > 0) {
  82. extr = right;
  83. }
  84. if (index !== extr) {
  85. temp = this._heap[index];
  86. this._heap[index] = this._heap[extr];
  87. this._heap[extr] = temp;
  88. this._heapify(extr);
  89. }
  90. };
  91. /**
  92. * Changes the key.<br><br>
  93. * Complexity: O(log N).
  94. *
  95. * @public
  96. * @param {Number} index Index of the value which should be changed.
  97. * @param {Number|Object} value New value according to the index.
  98. * @return {Number} New position of the element.
  99. */
  100. exports.Heap.prototype.changeKey = function (index, value) {
  101. this._heap[index] = value;
  102. var elem = this._heap[index];
  103. var parent = Math.floor(index / 2);
  104. var temp;
  105. if (elem !== undefined) {
  106. while (parent >= 0 && this._cmp(elem, this._heap[parent]) > 0) {
  107. temp = this._heap[parent];
  108. this._heap[parent] = elem;
  109. this._heap[index] = temp;
  110. index = parent;
  111. parent = Math.floor(parent / 2);
  112. }
  113. this._heapify(index);
  114. }
  115. return parent;
  116. };
  117. /**
  118. * Updates a given node. This operation is useful
  119. * in algorithms like Dijkstra, A* where we need
  120. * to decrease/increase value of the given node.
  121. *
  122. * @public
  123. * @param {Number|Object} node Node which should be updated.
  124. */
  125. exports.Heap.prototype.update = function (node) {
  126. var idx = this._heap.indexOf(node);
  127. if (idx >= 0) {
  128. this.changeKey(idx, node);
  129. }
  130. };
  131. /**
  132. * Adds new element to the heap.<br><br>
  133. * Complexity: O(log N).
  134. *
  135. * @public
  136. * @param {Number|Object} value Value which will be inserted.
  137. * @return {Number} Index of the inserted value.
  138. */
  139. exports.Heap.prototype.add = function (value) {
  140. this._heap.push(value);
  141. return this.changeKey(this._heap.length - 1, value);
  142. };
  143. /**
  144. * Returns current value which is on the top of the heap.<br><br>
  145. * Complexity: O(1).
  146. *
  147. * @public
  148. * @return {Number|Object} Current top value.
  149. */
  150. exports.Heap.prototype.top = function () {
  151. return this._heap[0];
  152. };
  153. /**
  154. * Removes and returns the current extremum value
  155. * which is on the top of the heap.<br><br>
  156. * Complexity: O(log N).
  157. *
  158. * @public
  159. * @returns {Number|Object} The extremum value.
  160. */
  161. exports.Heap.prototype.extract = function () {
  162. if (!this._heap.length) {
  163. throw 'The heap is already empty!';
  164. }
  165. var extr = this._heap.shift();
  166. this._heapify(0);
  167. return extr;
  168. };
  169. exports.Heap.prototype.getCollection = function () {
  170. return this._heap;
  171. };
  172. /**
  173. * Checks or heap is empty.
  174. *
  175. * @public
  176. * @returns {Boolean} Returns true if heap is empty.
  177. */
  178. exports.Heap.prototype.isEmpty = function () {
  179. return !this._heap.length;
  180. };
  181. })(typeof window === 'undefined' ? module.exports : window);