Pointer binary heap: A JavaScript binary heap implementation with pointers instead of arrays

pointer-binary-heap.js

/** Represents a node from a binary heap. */
class BinaryHeapNode {
  /**
   * Initializes a new instace of the `BinaryHeapNode` class.
   * @param {number} value
   * @param {*} ref
   */
  constructor(value, ref) {
    this.value = value;
    this.ref = ref;

    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

/** Represents a binary heap. */
class BinaryHeap {
  /**
   * Initializes a new instance of the `BinaryHeap` class.
   * @param {"min" | "max"} mode The binary heap mode. Defaults to `"min"`.
   */
  constructor(mode = "min") {
    this.mode = mode;

    this.root = null;
    this.size = 0;
  }

  /**
   * Adds a new value to the binary heap.
   * @param {number} value The value to add to the heap.
   * @param {*} ref An optional reference associated to the value.
   */
  add(value, ref = null) {
    let node = this._addNewNode(value, ref);
    while (node.parent && !this._heapCondition(node.parent, node)) {
      this._swapNodeValues(node, node.parent);
      node = node.parent;
    }
  }

  /** Removes the top of the heap. */
  remove() {
    if (this.size === 0) {
      return;
    }

    this._removeTailNode();
    if (this.size === 0) {
      return;
    }

    let node = this.root;
    while (
      (node.left && !this._heapCondition(node, node.left)) ||
      (node.right && !this._heapCondition(node, node.right))
    ) {
      if (!node.right || !this._heapCondition(node.right, node.left)) {
        this._swapNodeValues(node, node.left);
        node = node.left;
      } else {
        this._swapNodeValues(node, node.right);
        node = node.right;
      }
    }
  }

  /** Gets the top of the heap. */
  top() {
    if (this.root) {
      return {
        value: this.root.value,
        ref: this.root.ref,
      };
    }
  }

  /**
   * Adds a new node to the binary heap.
   * @param {number} value The number value of the node.
   * @param {*} ref A reference to an arbitrary value that the node will store.
   */
  _addNewNode(value, ref) {
    const node = new BinaryHeapNode(value, ref === null ? value : ref);

    if (this.root) {
      // add new tail node
      node.parent = this._getNewNodeParent();
      if (!node.parent.left) {
        node.parent.left = node;
      } else {
        node.parent.right = node;
      }
    } else {
      // add root node
      this.root = node;
    }

    ++this.size;
    return node;
  }

  /** Gets the parent for a new node in the binary heap. */
  _getNewNodeParent() {
    const stack = this._getNodeTraversalPath(this.size + 1);

    let node = this.root;
    while (stack.length > 1) {
      node = node[stack.pop()];
    }

    return node;
  }

  /**
   * Gets a stack that contains the path that must be traversed to reach a node.
   *
   * Binary heap trees have the following characteristics:
   * - Even node numbers are left children of their parent, odd node numbers are right children of their parent.
   * - A node parent's number is half of the children's node number.
   *
   * The following binary tree shows the node numbers of a tree of 7 nodes:
   *
   * ```
   *     1
   *  2     3
   * 4 5   6 7
   * ```
   *
   * @param {number} nodeNumber The node number to traverse to.
   * @return An Array (stack) with "left" or "right" strings indicating the path that must be traversed to reach the desired node.
   */
  _getNodeTraversalPath(nodeNumber) {
    const stack = [];

    let current = nodeNumber;
    while (current > 1) {
      if (current % 2 === 1) {
        // even node numbers are right childs
        stack.push("right");
      } else {
        // odd node numbers are left childs
        stack.push("left");
      }

      // move to parent
      current = Math.floor(current / 2);
    }

    return stack;
  }

  /** Gets the tail (rightmost, lowest level) node of a binary heap. */
  _getTailNode() {
    const stack = this._getNodeTraversalPath(this.size);

    let node = this.root;
    while (stack.length) {
      node = node[stack.pop()];
    }

    return node;
  }

  /**
   * Evaluates whether the heap condition is satisfied for two nodes.
   * @param {BinaryHeapNode} parent The parent node.
   * @param {BinaryHeapNode} child The child node.
   */
  _heapCondition(parent, child) {
    // in a min-heap, a parent must be <= than their child
    // in a max-heap, a parent must be >= than their child
    return this.mode === "min"
      ? parent.value <= child.value
      : parent.value >= child.value;
  }

  /** Removes the tail (rightmost, lowest level) node of a binary heap and swaps its values with the root node. */
  _removeTailNode() {
    if (this.size > 1) {
      // remove tail node
      const lastNode = this._getTailNode();
      if (lastNode.parent.left === lastNode) {
        lastNode.parent.left = null;
      } else {
        lastNode.parent.right = null;
      }

      this._swapNodeValues(lastNode, this.root);
    } else {
      // remove root node
      this.root = null;
    }

    --this.size;
  }

  /**
   * Swaps the values of two binary heap nodes.
   * @param {BinaryHeapNode} n1 The first node.
   * @param {BinaryHeapNode} n2 The second node.
   */
  _swapNodeValues(n1, n2) {
    const { ref, value } = n1;
    n1.ref = n2.ref;
    n1.value = n2.value;

    n2.ref = ref;
    n2.value = value;
  }
}