1 | import { factory } from '../../utils/factory.js';
|
2 | var name = 'FibonacciHeap';
|
3 | var dependencies = ['smaller', 'larger'];
|
4 | export var createFibonacciHeapClass = /* #__PURE__ */factory(name, dependencies, _ref => {
|
5 | var {
|
6 | smaller,
|
7 | larger
|
8 | } = _ref;
|
9 | var oneOverLogPhi = 1.0 / Math.log((1.0 + Math.sqrt(5.0)) / 2.0);
|
10 | /**
|
11 | * Fibonacci Heap implementation, used interally for Matrix math.
|
12 | * @class FibonacciHeap
|
13 | * @constructor FibonacciHeap
|
14 | */
|
15 |
|
16 | function FibonacciHeap() {
|
17 | if (!(this instanceof FibonacciHeap)) {
|
18 | throw new SyntaxError('Constructor must be called with the new operator');
|
19 | } // initialize fields
|
20 |
|
21 |
|
22 | this._minimum = null;
|
23 | this._size = 0;
|
24 | }
|
25 | /**
|
26 | * Attach type information
|
27 | */
|
28 |
|
29 |
|
30 | FibonacciHeap.prototype.type = 'FibonacciHeap';
|
31 | FibonacciHeap.prototype.isFibonacciHeap = true;
|
32 | /**
|
33 | * Inserts a new data element into the heap. No heap consolidation is
|
34 | * performed at this time, the new node is simply inserted into the root
|
35 | * list of this heap. Running time: O(1) actual.
|
36 | * @memberof FibonacciHeap
|
37 | */
|
38 |
|
39 | FibonacciHeap.prototype.insert = function (key, value) {
|
40 | // create node
|
41 | var node = {
|
42 | key,
|
43 | value,
|
44 | degree: 0
|
45 | }; // check we have a node in the minimum
|
46 |
|
47 | if (this._minimum) {
|
48 | // minimum node
|
49 | var minimum = this._minimum; // update left & right of node
|
50 |
|
51 | node.left = minimum;
|
52 | node.right = minimum.right;
|
53 | minimum.right = node;
|
54 | node.right.left = node; // update minimum node in heap if needed
|
55 |
|
56 | if (smaller(key, minimum.key)) {
|
57 | // node has a smaller key, use it as minimum
|
58 | this._minimum = node;
|
59 | }
|
60 | } else {
|
61 | // set left & right
|
62 | node.left = node;
|
63 | node.right = node; // this is the first node
|
64 |
|
65 | this._minimum = node;
|
66 | } // increment number of nodes in heap
|
67 |
|
68 |
|
69 | this._size++; // return node
|
70 |
|
71 | return node;
|
72 | };
|
73 | /**
|
74 | * Returns the number of nodes in heap. Running time: O(1) actual.
|
75 | * @memberof FibonacciHeap
|
76 | */
|
77 |
|
78 |
|
79 | FibonacciHeap.prototype.size = function () {
|
80 | return this._size;
|
81 | };
|
82 | /**
|
83 | * Removes all elements from this heap.
|
84 | * @memberof FibonacciHeap
|
85 | */
|
86 |
|
87 |
|
88 | FibonacciHeap.prototype.clear = function () {
|
89 | this._minimum = null;
|
90 | this._size = 0;
|
91 | };
|
92 | /**
|
93 | * Returns true if the heap is empty, otherwise false.
|
94 | * @memberof FibonacciHeap
|
95 | */
|
96 |
|
97 |
|
98 | FibonacciHeap.prototype.isEmpty = function () {
|
99 | return this._size === 0;
|
100 | };
|
101 | /**
|
102 | * Extracts the node with minimum key from heap. Amortized running
|
103 | * time: O(log n).
|
104 | * @memberof FibonacciHeap
|
105 | */
|
106 |
|
107 |
|
108 | FibonacciHeap.prototype.extractMinimum = function () {
|
109 | // node to remove
|
110 | var node = this._minimum; // check we have a minimum
|
111 |
|
112 | if (node === null) {
|
113 | return node;
|
114 | } // current minimum
|
115 |
|
116 |
|
117 | var minimum = this._minimum; // get number of children
|
118 |
|
119 | var numberOfChildren = node.degree; // pointer to the first child
|
120 |
|
121 | var x = node.child; // for each child of node do...
|
122 |
|
123 | while (numberOfChildren > 0) {
|
124 | // store node in right side
|
125 | var tempRight = x.right; // remove x from child list
|
126 |
|
127 | x.left.right = x.right;
|
128 | x.right.left = x.left; // add x to root list of heap
|
129 |
|
130 | x.left = minimum;
|
131 | x.right = minimum.right;
|
132 | minimum.right = x;
|
133 | x.right.left = x; // set Parent[x] to null
|
134 |
|
135 | x.parent = null;
|
136 | x = tempRight;
|
137 | numberOfChildren--;
|
138 | } // remove node from root list of heap
|
139 |
|
140 |
|
141 | node.left.right = node.right;
|
142 | node.right.left = node.left; // update minimum
|
143 |
|
144 | if (node === node.right) {
|
145 | // empty
|
146 | minimum = null;
|
147 | } else {
|
148 | // update minimum
|
149 | minimum = node.right; // we need to update the pointer to the root with minimum key
|
150 |
|
151 | minimum = _findMinimumNode(minimum, this._size);
|
152 | } // decrement size of heap
|
153 |
|
154 |
|
155 | this._size--; // update minimum
|
156 |
|
157 | this._minimum = minimum; // return node
|
158 |
|
159 | return node;
|
160 | };
|
161 | /**
|
162 | * Removes a node from the heap given the reference to the node. The trees
|
163 | * in the heap will be consolidated, if necessary. This operation may fail
|
164 | * to remove the correct element if there are nodes with key value -Infinity.
|
165 | * Running time: O(log n) amortized.
|
166 | * @memberof FibonacciHeap
|
167 | */
|
168 |
|
169 |
|
170 | FibonacciHeap.prototype.remove = function (node) {
|
171 | // decrease key value
|
172 | this._minimum = _decreaseKey(this._minimum, node, -1); // remove the smallest
|
173 |
|
174 | this.extractMinimum();
|
175 | };
|
176 | /**
|
177 | * Decreases the key value for a heap node, given the new value to take on.
|
178 | * The structure of the heap may be changed and will not be consolidated.
|
179 | * Running time: O(1) amortized.
|
180 | * @memberof FibonacciHeap
|
181 | */
|
182 |
|
183 |
|
184 | function _decreaseKey(minimum, node, key) {
|
185 | // set node key
|
186 | node.key = key; // get parent node
|
187 |
|
188 | var parent = node.parent;
|
189 |
|
190 | if (parent && smaller(node.key, parent.key)) {
|
191 | // remove node from parent
|
192 | _cut(minimum, node, parent); // remove all nodes from parent to the root parent
|
193 |
|
194 |
|
195 | _cascadingCut(minimum, parent);
|
196 | } // update minimum node if needed
|
197 |
|
198 |
|
199 | if (smaller(node.key, minimum.key)) {
|
200 | minimum = node;
|
201 | } // return minimum
|
202 |
|
203 |
|
204 | return minimum;
|
205 | }
|
206 | /**
|
207 | * The reverse of the link operation: removes node from the child list of parent.
|
208 | * This method assumes that min is non-null. Running time: O(1).
|
209 | * @memberof FibonacciHeap
|
210 | */
|
211 |
|
212 |
|
213 | function _cut(minimum, node, parent) {
|
214 | // remove node from parent children and decrement Degree[parent]
|
215 | node.left.right = node.right;
|
216 | node.right.left = node.left;
|
217 | parent.degree--; // reset y.child if necessary
|
218 |
|
219 | if (parent.child === node) {
|
220 | parent.child = node.right;
|
221 | } // remove child if degree is 0
|
222 |
|
223 |
|
224 | if (parent.degree === 0) {
|
225 | parent.child = null;
|
226 | } // add node to root list of heap
|
227 |
|
228 |
|
229 | node.left = minimum;
|
230 | node.right = minimum.right;
|
231 | minimum.right = node;
|
232 | node.right.left = node; // set parent[node] to null
|
233 |
|
234 | node.parent = null; // set mark[node] to false
|
235 |
|
236 | node.mark = false;
|
237 | }
|
238 | /**
|
239 | * Performs a cascading cut operation. This cuts node from its parent and then
|
240 | * does the same for its parent, and so on up the tree.
|
241 | * Running time: O(log n); O(1) excluding the recursion.
|
242 | * @memberof FibonacciHeap
|
243 | */
|
244 |
|
245 |
|
246 | function _cascadingCut(minimum, node) {
|
247 | // store parent node
|
248 | var parent = node.parent; // if there's a parent...
|
249 |
|
250 | if (!parent) {
|
251 | return;
|
252 | } // if node is unmarked, set it marked
|
253 |
|
254 |
|
255 | if (!node.mark) {
|
256 | node.mark = true;
|
257 | } else {
|
258 | // it's marked, cut it from parent
|
259 | _cut(minimum, node, parent); // cut its parent as well
|
260 |
|
261 |
|
262 | _cascadingCut(parent);
|
263 | }
|
264 | }
|
265 | /**
|
266 | * Make the first node a child of the second one. Running time: O(1) actual.
|
267 | * @memberof FibonacciHeap
|
268 | */
|
269 |
|
270 |
|
271 | var _linkNodes = function _linkNodes(node, parent) {
|
272 | // remove node from root list of heap
|
273 | node.left.right = node.right;
|
274 | node.right.left = node.left; // make node a Child of parent
|
275 |
|
276 | node.parent = parent;
|
277 |
|
278 | if (!parent.child) {
|
279 | parent.child = node;
|
280 | node.right = node;
|
281 | node.left = node;
|
282 | } else {
|
283 | node.left = parent.child;
|
284 | node.right = parent.child.right;
|
285 | parent.child.right = node;
|
286 | node.right.left = node;
|
287 | } // increase degree[parent]
|
288 |
|
289 |
|
290 | parent.degree++; // set mark[node] false
|
291 |
|
292 | node.mark = false;
|
293 | };
|
294 |
|
295 | function _findMinimumNode(minimum, size) {
|
296 | // to find trees of the same degree efficiently we use an array of length O(log n) in which we keep a pointer to one root of each degree
|
297 | var arraySize = Math.floor(Math.log(size) * oneOverLogPhi) + 1; // create list with initial capacity
|
298 |
|
299 | var array = new Array(arraySize); // find the number of root nodes.
|
300 |
|
301 | var numRoots = 0;
|
302 | var x = minimum;
|
303 |
|
304 | if (x) {
|
305 | numRoots++;
|
306 | x = x.right;
|
307 |
|
308 | while (x !== minimum) {
|
309 | numRoots++;
|
310 | x = x.right;
|
311 | }
|
312 | } // vars
|
313 |
|
314 |
|
315 | var y; // For each node in root list do...
|
316 |
|
317 | while (numRoots > 0) {
|
318 | // access this node's degree..
|
319 | var d = x.degree; // get next node
|
320 |
|
321 | var next = x.right; // check if there is a node already in array with the same degree
|
322 |
|
323 | while (true) {
|
324 | // get node with the same degree is any
|
325 | y = array[d];
|
326 |
|
327 | if (!y) {
|
328 | break;
|
329 | } // make one node with the same degree a child of the other, do this based on the key value.
|
330 |
|
331 |
|
332 | if (larger(x.key, y.key)) {
|
333 | var temp = y;
|
334 | y = x;
|
335 | x = temp;
|
336 | } // make y a child of x
|
337 |
|
338 |
|
339 | _linkNodes(y, x); // we have handled this degree, go to next one.
|
340 |
|
341 |
|
342 | array[d] = null;
|
343 | d++;
|
344 | } // save this node for later when we might encounter another of the same degree.
|
345 |
|
346 |
|
347 | array[d] = x; // move forward through list.
|
348 |
|
349 | x = next;
|
350 | numRoots--;
|
351 | } // Set min to null (effectively losing the root list) and reconstruct the root list from the array entries in array[].
|
352 |
|
353 |
|
354 | minimum = null; // loop nodes in array
|
355 |
|
356 | for (var i = 0; i < arraySize; i++) {
|
357 | // get current node
|
358 | y = array[i];
|
359 |
|
360 | if (!y) {
|
361 | continue;
|
362 | } // check if we have a linked list
|
363 |
|
364 |
|
365 | if (minimum) {
|
366 | // First remove node from root list.
|
367 | y.left.right = y.right;
|
368 | y.right.left = y.left; // now add to root list, again.
|
369 |
|
370 | y.left = minimum;
|
371 | y.right = minimum.right;
|
372 | minimum.right = y;
|
373 | y.right.left = y; // check if this is a new min.
|
374 |
|
375 | if (smaller(y.key, minimum.key)) {
|
376 | minimum = y;
|
377 | }
|
378 | } else {
|
379 | minimum = y;
|
380 | }
|
381 | }
|
382 |
|
383 | return minimum;
|
384 | }
|
385 |
|
386 | return FibonacciHeap;
|
387 | }, {
|
388 | isClass: true
|
389 | }); |
\ | No newline at end of file |