Debian Codegraph @

closure-library/closure/goog/structs/heap.js

raw
1 // Copyright 2006 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview Datastructure: Heap.
17 *
18 *
19 * This file provides the implementation of a Heap datastructure. Smaller keys
20 * rise to the top.
21 *
22 * The big-O notation for all operations are below:
23 * <pre>
24 * Method big-O
25 * ----------------------------------------------------------------------------
26 * - insert O(logn)
27 * - remove O(logn)
28 * - peek O(1)
29 * - contains O(n)
30 * </pre>
31 */
32 // TODO(user): Should this rely on natural ordering via some Comparable
33 // interface?
34
35
36 goog.provide('goog.structs.Heap');
37
38 goog.require('goog.array');
39 goog.require('goog.object');
40 goog.require('goog.structs.Node');
41
42
43
44 /**
45 * Class for a Heap datastructure.
46 *
47 * @param {goog.structs.Heap|Object=} opt_heap Optional goog.structs.Heap or
48 * Object to initialize heap with.
49 * @constructor
50 * @template K, V
51 */
52 goog.structs.Heap = function(opt_heap) {
53 /**
54 * The nodes of the heap.
55 * @private
56 * @type {Array<goog.structs.Node>}
57 */
58 this.nodes_ = [];
59
60 if (opt_heap) {
61 this.insertAll(opt_heap);
62 }
63 };
64
65
66 /**
67 * Insert the given value into the heap with the given key.
68 * @param {K} key The key.
69 * @param {V} value The value.
70 */
71 goog.structs.Heap.prototype.insert = function(key, value) {
72 var node = new goog.structs.Node(key, value);
73 var nodes = this.nodes_;
74 nodes.push(node);
75 this.moveUp_(nodes.length - 1);
76 };
77
78
79 /**
80 * Adds multiple key-value pairs from another goog.structs.Heap or Object
81 * @param {goog.structs.Heap|Object} heap Object containing the data to add.
82 */
83 goog.structs.Heap.prototype.insertAll = function(heap) {
84 var keys, values;
85 if (heap instanceof goog.structs.Heap) {
86 keys = heap.getKeys();
87 values = heap.getValues();
88
89 // If it is a heap and the current heap is empty, I can rely on the fact
90 // that the keys/values are in the correct order to put in the underlying
91 // structure.
92 if (this.getCount() <= 0) {
93 var nodes = this.nodes_;
94 for (var i = 0; i < keys.length; i++) {
95 nodes.push(new goog.structs.Node(keys[i], values[i]));
96 }
97 return;
98 }
99 } else {
100 keys = goog.object.getKeys(heap);
101 values = goog.object.getValues(heap);
102 }
103
104 for (var i = 0; i < keys.length; i++) {
105 this.insert(keys[i], values[i]);
106 }
107 };
108
109
110 /**
111 * Retrieves and removes the root value of this heap.
112 * @return {V} The value removed from the root of the heap. Returns
113 * undefined if the heap is empty.
114 */
115 goog.structs.Heap.prototype.remove = function() {
116 var nodes = this.nodes_;
117 var count = nodes.length;
118 var rootNode = nodes[0];
119 if (count <= 0) {
120 return undefined;
121 } else if (count == 1) {
122 goog.array.clear(nodes);
123 } else {
124 nodes[0] = nodes.pop();
125 this.moveDown_(0);
126 }
127 return rootNode.getValue();
128 };
129
130
131 /**
132 * Retrieves but does not remove the root value of this heap.
133 * @return {V} The value at the root of the heap. Returns
134 * undefined if the heap is empty.
135 */
136 goog.structs.Heap.prototype.peek = function() {
137 var nodes = this.nodes_;
138 if (nodes.length == 0) {
139 return undefined;
140 }
141 return nodes[0].getValue();
142 };
143
144
145 /**
146 * Retrieves but does not remove the key of the root node of this heap.
147 * @return {K} The key at the root of the heap. Returns undefined if the
148 * heap is empty.
149 */
150 goog.structs.Heap.prototype.peekKey = function() {
151 return this.nodes_[0] && this.nodes_[0].getKey();
152 };
153
154
155 /**
156 * Moves the node at the given index down to its proper place in the heap.
157 * @param {number} index The index of the node to move down.
158 * @private
159 */
160 goog.structs.Heap.prototype.moveDown_ = function(index) {
161 var nodes = this.nodes_;
162 var count = nodes.length;
163
164 // Save the node being moved down.
165 var node = nodes[index];
166 // While the current node has a child.
167 while (index < (count >> 1)) {
168 var leftChildIndex = this.getLeftChildIndex_(index);
169 var rightChildIndex = this.getRightChildIndex_(index);
170
171 // Determine the index of the smaller child.
172 var smallerChildIndex = rightChildIndex < count &&
173 nodes[rightChildIndex].getKey() < nodes[leftChildIndex].getKey() ?
174 rightChildIndex :
175 leftChildIndex;
176
177 // If the node being moved down is smaller than its children, the node
178 // has found the correct index it should be at.
179 if (nodes[smallerChildIndex].getKey() > node.getKey()) {
180 break;
181 }
182
183 // If not, then take the smaller child as the current node.
184 nodes[index] = nodes[smallerChildIndex];
185 index = smallerChildIndex;
186 }
187 nodes[index] = node;
188 };
189
190
191 /**
192 * Moves the node at the given index up to its proper place in the heap.
193 * @param {number} index The index of the node to move up.
194 * @private
195 */
196 goog.structs.Heap.prototype.moveUp_ = function(index) {
197 var nodes = this.nodes_;
198 var node = nodes[index];
199
200 // While the node being moved up is not at the root.
201 while (index > 0) {
202 // If the parent is less than the node being moved up, move the parent down.
203 var parentIndex = this.getParentIndex_(index);
204 if (nodes[parentIndex].getKey() > node.getKey()) {
205 nodes[index] = nodes[parentIndex];
206 index = parentIndex;
207 } else {
208 break;
209 }
210 }
211 nodes[index] = node;
212 };
213
214
215 /**
216 * Gets the index of the left child of the node at the given index.
217 * @param {number} index The index of the node to get the left child for.
218 * @return {number} The index of the left child.
219 * @private
220 */
221 goog.structs.Heap.prototype.getLeftChildIndex_ = function(index) {
222 return index * 2 + 1;
223 };
224
225
226 /**
227 * Gets the index of the right child of the node at the given index.
228 * @param {number} index The index of the node to get the right child for.
229 * @return {number} The index of the right child.
230 * @private
231 */
232 goog.structs.Heap.prototype.getRightChildIndex_ = function(index) {
233 return index * 2 + 2;
234 };
235
236
237 /**
238 * Gets the index of the parent of the node at the given index.
239 * @param {number} index The index of the node to get the parent for.
240 * @return {number} The index of the parent.
241 * @private
242 */
243 goog.structs.Heap.prototype.getParentIndex_ = function(index) {
244 return (index - 1) >> 1;
245 };
246
247
248 /**
249 * Gets the values of the heap.
250 * @return {!Array<V>} The values in the heap.
251 */
252 goog.structs.Heap.prototype.getValues = function() {
253 var nodes = this.nodes_;
254 var rv = [];
255 var l = nodes.length;
256 for (var i = 0; i < l; i++) {
257 rv.push(nodes[i].getValue());
258 }
259 return rv;
260 };
261
262
263 /**
264 * Gets the keys of the heap.
265 * @return {!Array<K>} The keys in the heap.
266 */
267 goog.structs.Heap.prototype.getKeys = function() {
268 var nodes = this.nodes_;
269 var rv = [];
270 var l = nodes.length;
271 for (var i = 0; i < l; i++) {
272 rv.push(nodes[i].getKey());
273 }
274 return rv;
275 };
276
277
278 /**
279 * Whether the heap contains the given value.
280 * @param {V} val The value to check for.
281 * @return {boolean} Whether the heap contains the value.
282 */
283 goog.structs.Heap.prototype.containsValue = function(val) {
284 return goog.array.some(
285 this.nodes_, function(node) { return node.getValue() == val; });
286 };
287
288
289 /**
290 * Whether the heap contains the given key.
291 * @param {K} key The key to check for.
292 * @return {boolean} Whether the heap contains the key.
293 */
294 goog.structs.Heap.prototype.containsKey = function(key) {
295 return goog.array.some(
296 this.nodes_, function(node) { return node.getKey() == key; });
297 };
298
299
300 /**
301 * Clones a heap and returns a new heap
302 * @return {!goog.structs.Heap} A new goog.structs.Heap with the same key-value
303 * pairs.
304 */
305 goog.structs.Heap.prototype.clone = function() {
306 return new goog.structs.Heap(this);
307 };
308
309
310 /**
311 * The number of key-value pairs in the map
312 * @return {number} The number of pairs.
313 */
314 goog.structs.Heap.prototype.getCount = function() {
315 return this.nodes_.length;
316 };
317
318
319 /**
320 * Returns true if this heap contains no elements.
321 * @return {boolean} Whether this heap contains no elements.
322 */
323 goog.structs.Heap.prototype.isEmpty = function() {
324 return goog.array.isEmpty(this.nodes_);
325 };
326
327
328 /**
329 * Removes all elements from the heap.
330 */
331 goog.structs.Heap.prototype.clear = function() {
332 goog.array.clear(this.nodes_);
333 };