https://skylandx.ai/libs/other/BinaryHeap.js

1/*
2** Binary Heap implementation in Javascript
3** From: http://eloquentjavascript.net/1st_edition/appendix2.html
4**
5** Copyright (c) 2007 Marijn Haverbeke, last modified on November 28 2013.
6**
7** Licensed under a Creative Commons attribution-noncommercial license. 
8** All code in this book may also be considered licensed under an MIT license.
9*/
10
11
12
13function BinaryHeap(scoreFunction){
14  this.content = [];
15  this.scoreFunction = scoreFunction;
16}
17
18BinaryHeap.prototype = {
19  push: function(element) {
20    // Add the new element to the end of the array.
21    this.content.push(element);
22    // Allow it to bubble up.
23    this.bubbleUp(this.content.length - 1);
24  },
25
26  pop: function() {
27    // Store the first element so we can return it later.
28    var result = this.content[0];
29    // Get the element at the end of the array.
30    var end = this.content.pop();
31    // If there are any elements left, put the end element at the
32    // start, and let it sink down.
33    if (this.content.length > 0) {
34      this.content[0] = end;
35      this.sinkDown(0);
36    }
37    return result;
38  },
39
40  remove: function(node) {
41    var length = this.content.length;
42    // To remove a value, we must search through the array to find
43    // it.
44    for (var i = 0; i < length; i++) {
45      if (this.content[i] != node) continue;
46      // When it is found, the process seen in 'pop' is repeated
47      // to fill up the hole.
48      var end = this.content.pop();
49      // If the element we popped was the one we needed to remove,
50      // we're done.
51      if (i == length - 1) break;
52      // Otherwise, we replace the removed element with the popped
53      // one, and allow it to float up or sink down as appropriate.
54      this.content[i] = end;
55      this.bubbleUp(i);
56      this.sinkDown(i);
57      break;
58    }
59  },
60
61  size: function() {
62    return this.content.length;
63  },
64
65  bubbleUp: function(n) {
66    // Fetch the element that has to be moved.
67    var element = this.content[n], score = this.scoreFunction(element);
68    // When at 0, an element can not go up any further.
69    while (n > 0) {
70      // Compute the parent element's index, and fetch it.
71      var parentN = Math.floor((n + 1) / 2) - 1,
72      parent = this.content[parentN];
73      // If the parent has a lesser score, things are in order and we
74      // are done.
75      if (score >= this.scoreFunction(parent))
76        break;
77
78      // Otherwise, swap the parent with the current element and
79      // continue.
80      this.content[parentN] = element;
81      this.content[n] = parent;
82      n = parentN;
83    }
84  },
85
86  sinkDown: function(n) {
87    // Look up the target element and its score.
88    var length = this.content.length,
89    element = this.content[n],
90    elemScore = this.scoreFunction(element);
91
92    while(true) {
93      // Compute the indices of the child elements.
94      var child2N = (n + 1) * 2, child1N = child2N - 1;
95      // This is used to store the new position of the element,
96      // if any.
97      var swap = null;
98      // If the first child exists (is inside the array)...
99      if (child1N < length) {
100        // Look it up and compute its score.
101        var child1 = this.content[child1N],
102        child1Score = this.scoreFunction(child1);
103        // If the score is less than our element's, we need to swap.
104        if (child1Score < elemScore)
105          swap = child1N;
106      }
107      // Do the same checks for the other child.
108      if (child2N < length) {
109        var child2 = this.content[child2N],
110        child2Score = this.scoreFunction(child2);
111        if (child2Score < (swap == null ? elemScore : child1Score))
112          swap = child2N;
113      }
114
115      // No need to swap further, we are done.
116      if (swap == null) break;
117
118      // Otherwise, swap and continue.
119      this.content[n] = this.content[swap];
120      this.content[swap] = element;
121      n = swap;
122    }
123  }
124};