Skip to content

Commit 83a1557

Browse files
mgechevmgechev
committed
Add more docs
1 parent a4ec220 commit 83a1557

27 files changed

+5402
-38
lines changed

‎data-structures_binary-search-tree.js.html‎

Lines changed: 475 additions & 0 deletions
Large diffs are not rendered by default.

‎data-structures_heap.js.html‎

Lines changed: 242 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,242 @@
1+
<!DOCTYPE html>
2+
<html lang="en">
3+
<head>
4+
<meta charset="utf-8">
5+
<title>JSDoc: Source: data-structures/heap.js</title>
6+
7+
<script src="scripts/prettify/prettify.js"> </script>
8+
<script src="scripts/prettify/lang-css.js"> </script>
9+
<!--[if lt IE 9]>
10+
<script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script>
11+
<![endif]-->
12+
<link type="text/css" rel="stylesheet" href="styles/prettify-tomorrow.css">
13+
<link type="text/css" rel="stylesheet" href="styles/jsdoc-default.css">
14+
</head>
15+
16+
<body>
17+
18+
<div id="main">
19+
20+
<h1 class="page-title">Source: data-structures/heap.js</h1>
21+
22+
23+
24+
25+
26+
27+
<section>
28+
<article>
29+
<pre class="prettyprint source linenums"><code>/**
30+
* A binary heap is a complete binary tree which satisfies the heap ordering property.
31+
*
32+
* @example
33+
* var Heap = require('path-to-algorithms/src/data-structures/heap').Heap;
34+
*
35+
* var heap = new Heap(function(a, b) {
36+
* return a.birthyear - b.birthyear;
37+
* });
38+
*
39+
* heap.add({
40+
* name: 'John',
41+
* birthyear: 1981
42+
* });
43+
* heap.add({
44+
* name: 'Pavlo',
45+
* birthyear: 2000
46+
* });
47+
* heap.add({
48+
* name: 'Garry',
49+
* birthyear: 1989
50+
* });
51+
* heap.add({
52+
* name: 'Derek',
53+
* birthyear: 1990
54+
* });
55+
* heap.add({
56+
* name: 'Ivan',
57+
* birthyear: 1966
58+
* });
59+
*
60+
* console.log(heap.extract()); // { name: 'Pavlo', birthyear: 2000 }
61+
* console.log(heap.extract()); // { name: 'Derek', birthyear: 1990 }
62+
* console.log(heap.extract()); // { name: 'Garry', birthyear: 1989 }
63+
* console.log(heap.extract()); // { name: 'John', birthyear: 1981 }
64+
* console.log(heap.extract()); // { name: 'Ivan', birthyear: 1966 }
65+
*
66+
* @module data-structures/heap
67+
*/
68+
(function (exports) {
69+
70+
'use strict';
71+
72+
/**
73+
* Minimum heap constructor.
74+
*
75+
* @public
76+
* @constructor
77+
* @param {Function} cmp Function used for comparition between the elements.
78+
*/
79+
exports.Heap = function(cmp) {
80+
this._heap = [];
81+
if (typeof cmp === 'function') {
82+
this._cmp = cmp;
83+
} else {
84+
this._cmp = function (a, b) {
85+
return a - b;
86+
};
87+
}
88+
}
89+
90+
/**
91+
* Exchange indexes with start index given as argument
92+
* to turn the tree into a valid heap. On a single call
93+
* this method maintains only a single "branch" of the heap.&lt;br>&lt;br>
94+
*
95+
* Time complexity: O(log N).
96+
*
97+
* @private
98+
* @param {Number} index The parent.
99+
*/
100+
exports.Heap.prototype._heapify = function (index) {
101+
var extr = index,
102+
left = 2 * index + 1,
103+
right = 2 * index + 2,
104+
temp;
105+
106+
if (left &lt; this._heap.length &amp;&amp;
107+
this._cmp(this._heap[left], this._heap[index]) > 0) {
108+
extr = left;
109+
}
110+
111+
if (right &lt; this._heap.length &amp;&amp;
112+
this._cmp(this._heap[right], this._heap[index]) > 0) {
113+
extr = right;
114+
}
115+
116+
if (index !== extr) {
117+
temp = this._heap[index];
118+
this._heap[index] = this._heap[extr];
119+
this._heap[extr] = temp;
120+
this._heapify(extr);
121+
}
122+
};
123+
124+
/**
125+
* Changes the key.&lt;br>&lt;br>
126+
* Complexity: O(log N).
127+
*
128+
* @public
129+
* @param {Number} index Index of the value which should be changed.
130+
* @param {Number|Object} value New value according to the index.
131+
* @return {Number} New position of the element.
132+
*/
133+
exports.Heap.prototype.changeKey = function (index, value) {
134+
this._heap[index] = value;
135+
var elem = this._heap[index],
136+
parent = Math.floor(index / 2),
137+
temp;
138+
if (elem !== undefined) {
139+
while (parent >= 0 &amp;&amp; this._cmp(elem, this._heap[parent]) > 0) {
140+
temp = this._heap[parent];
141+
this._heap[parent] = elem;
142+
this._heap[index] = temp;
143+
index = parent;
144+
parent = Math.floor(parent / 2);
145+
}
146+
}
147+
return parent;
148+
};
149+
150+
/**
151+
* Updates a given node. This operation is useful
152+
* in algorithms like Dijkstra, A* where we need
153+
* to decrease/increase value of the given node.
154+
*
155+
* @public
156+
* @param {Number|Object} node Node which should be updated.
157+
*/
158+
exports.Heap.prototype.update = function (node) {
159+
var idx = this._heap.indexOf(node);
160+
if (idx >= 0) {
161+
this.changeKey(idx, node);
162+
}
163+
};
164+
165+
/**
166+
* Adds new element to the heap.&lt;br>&lt;br>
167+
* Complexity: O(log N).
168+
*
169+
* @public
170+
* @param {Number|Object} value Value which will be inserted.
171+
* @return {Number} Index of the inserted value.
172+
*/
173+
exports.Heap.prototype.add = function (value) {
174+
this._heap.push(value);
175+
return this.changeKey(this._heap.length - 1, value);
176+
};
177+
178+
/**
179+
* Returns current value which is on the top of the heap.&lt;br>&lt;br>
180+
* Complexity: O(1).
181+
*
182+
* @public
183+
* @return {Number|Object} Current top value.
184+
*/
185+
exports.Heap.prototype.top = function () {
186+
return this._heap[0];
187+
};
188+
189+
/**
190+
* Removes and returns the current extremum value
191+
* which is on the top of the heap.&lt;br>&lt;br>
192+
* Complexity: O(log N).
193+
*
194+
* @public
195+
* @returns {Number|Object} The extremum value.
196+
*/
197+
exports.Heap.prototype.extract = function () {
198+
if (!this._heap.length) {
199+
throw 'The heap is already empty!';
200+
}
201+
var extr = this._heap.shift();
202+
this._heapify(0);
203+
return extr;
204+
};
205+
206+
exports.Heap.prototype.getCollection = function () {
207+
return this._heap;
208+
};
209+
210+
/**
211+
* Checks or heap is empty.
212+
*
213+
* @public
214+
* @returns {Boolean} Returns true if heap is empty.
215+
*/
216+
exports.Heap.prototype.isEmpty = function () {
217+
return !this._heap.length;
218+
};
219+
220+
})(typeof window === 'undefined' ? module.exports : window);</code></pre>
221+
</article>
222+
</section>
223+
224+
225+
226+
227+
</div>
228+
229+
<nav>
230+
<h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-data-structures_binary-search-tree.html">data-structures/binary-search-tree</a></li><li><a href="module-data-structures_heap.html">data-structures/heap</a></li><li><a href="module-graphs_others_topological-sort.html">graphs/others/topological-sort</a></li><li><a href="module-graphs_searching_bfs.html">graphs/searching/bfs</a></li><li><a href="module-graphs_searching_dfs.html">graphs/searching/dfs</a></li><li><a href="module-graphs_shortest-path_bellman-ford.html">graphs/shortest-path/bellman-ford</a></li><li><a href="module-graphs_shortest-path_dijkstra.html">graphs/shortest-path/dijkstra</a></li><li><a href="module-graphs_shortest-path_floyd-warshall.html">graphs/shortest-path/floyd-warshall</a></li><li><a href="module-graphs_spanning-trees_prim.html">graphs/spanning-trees/prim</a></li></ul><h3>Classes</h3><ul><li><a href="module-data-structures_binary-search-tree.BinaryTree.html">BinaryTree</a></li><li><a href="module-data-structures_binary-search-tree.Node.html">Node</a></li><li><a href="module-data-structures_heap.Heap.html">Heap</a></li><li><a href="module-graphs_shortest-path_bellman-ford.Edge.html">Edge</a></li><li><a href="module-graphs_spanning-trees_prim.Edge.html">Edge</a></li><li><a href="module-graphs_spanning-trees_prim.Graph.html">Graph</a></li><li><a href="module-graphs_spanning-trees_prim.Vertex.html">Vertex</a></li></ul>
231+
</nav>
232+
233+
<br class="clear">
234+
235+
<footer>
236+
Documentation generated by <a href="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> on Sat Jan 10 2015 15:37:24 GMT+0200 (EET)
237+
</footer>
238+
239+
<script> prettyPrint(); </script>
240+
<script src="scripts/linenumber.js"> </script>
241+
</body>
242+
</html>

0 commit comments

Comments
 (0)