src/utils/binary-heap.js

/**
 * @file Binary Heap
 * @author Alexander Rose <alexander.rose@weirdbyte.de>
 * @private
 */

/**
 * Binary heap implementation
 * @class
 * @author http://eloquentjavascript.net/appendix2.htm
 * @param {Function} scoreFunction - the heap scoring function
 */
function BinaryHeap (scoreFunction) {
  this.content = []
  this.scoreFunction = scoreFunction
}

BinaryHeap.prototype = {

  push: function (element) {
        // Add the new element to the end of the array.
    this.content.push(element)

        // Allow it to bubble up.
    this.bubbleUp(this.content.length - 1)
  },

  pop: function () {
        // Store the first element so we can return it later.
    var result = this.content[ 0 ]

        // Get the element at the end of the array.
    var end = this.content.pop()

        // If there are any elements left, put the end element at the
        // start, and let it sink down.
    if (this.content.length > 0) {
      this.content[ 0 ] = end
      this.sinkDown(0)
    }

    return result
  },

  peek: function () {
    return this.content[ 0 ]
  },

  remove: function (node) {
    var len = this.content.length

        // To remove a value, we must search through the array to find it.
    for (var i = 0; i < len; i++) {
      if (this.content[ i ] === node) {
                // When it is found, the process seen in 'pop' is repeated
                // to fill up the hole.
        var end = this.content.pop()

        if (i !== len - 1) {
          this.content[ i ] = end

          if (this.scoreFunction(end) < this.scoreFunction(node)) {
            this.bubbleUp(i)
          } else {
            this.sinkDown(i)
          }
        }

        return
      }
    }

    throw new Error('Node not found.')
  },

  size: function () {
    return this.content.length
  },

  bubbleUp: function (n) {
        // Fetch the element that has to be moved.
    var element = this.content[ n ]

        // When at 0, an element can not go up any further.
    while (n > 0) {
            // Compute the parent element's index, and fetch it.
      var parentN = Math.floor((n + 1) / 2) - 1
      var parent = this.content[ parentN ]

            // Swap the elements if the parent is greater.
      if (this.scoreFunction(element) < this.scoreFunction(parent)) {
        this.content[ parentN ] = element
        this.content[ n ] = parent

                // Update 'n' to continue at the new position.
        n = parentN
      } else {
                // Found a parent that is less, no need to move it further.
        break
      }
    }
  },

  sinkDown: function (n) {
        // Look up the target element and its score.
    var length = this.content.length
    var element = this.content[ n ]
    var elemScore = this.scoreFunction(element)

    var child1Score, child2Score

    while (true) {
            // Compute the indices of the child elements.
      var child2N = (n + 1) * 2
      var child1N = child2N - 1

            // This is used to store the new position of the element, if any.
      var swap = null

            // If the first child exists (is inside the array)...
      if (child1N < length) {
                // Look it up and compute its score.
        var child1 = this.content[ child1N ]
        child1Score = this.scoreFunction(child1)

                // If the score is less than our element's, we need to swap.
        if (child1Score < elemScore) swap = child1N
      }

            // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.content[ child2N ]
        child2Score = this.scoreFunction(child2)

        if (child2Score < (swap === null ? elemScore : child1Score)) swap = child2N
      }

            // If the element needs to be moved, swap it, and continue.
      if (swap !== null) {
        this.content[ n ] = this.content[ swap ]
        this.content[ swap ] = element
        n = swap
      } else {
                // Otherwise, we are done.
        break
      }
    }
  }

}

export default BinaryHeap