maxHeap.js

/**
 * Max Heap.
 * 
 * @example const MaxHeap = require('dstructures').MaxHeap;
 * const myMaxHeap = new MaxHeap();
 * @description This is "max" implementation so, larger numbers have priority!
 * For "min" implementation where lower numbers have priority, use PriorityQueueMin.
 * @description In computer science, a heap is a specialized tree-based data 
 * structure that satisfies the heap property: if P is a parent node of C, then the 
 * key (the value) of P is either greater than or equal to (in a max heap) or less 
 * than or equal to (in a min heap) the key of C.[1] The node at the "top" of the 
 * heap (with no parents) is called the root node. Full wikipedia article at: 
 * {@link https://en.wikipedia.org/wiki/Heap_(data_structure)}
 * @public
 * @constructor
 * @class
 */
class MaxHeap {

  constructor(){
    // Underlying array
    // @private
    this._container = [null];
  }

  /**
   * Inserts element in a heap.
   * 
   * @param {any} element Given element.
   * @param {Number} [priority = 0] Priority defaults to 0 if is not present.
   * @returns {Boolean|Void} Returns false if 'priority' is not number or 
   * 'element' is undefined or null.
   * @example MaxHeap.insert('Cat', 1); // ['Cat']
   * MaxHeap.insert('Dog', 2); // ['Dog', 'Cat']
   * @memberOf MaxHeap
   */
  insert (element, priority) {
    // No priority is given if priority argument is ommited or different type.
    if (typeof(priority) !== 'number') {
      priority = 0;
    }
    // If element argument is not present
    if (!element) {
      return false;
    }
    // Push the new node
    const newNode = new _Node (element, priority);
    this._container.push(newNode);
    // Get the curreent index and the parent index
    let currNodeIndex = this._container.length - 1;
    let parentNodeIndex = Math.floor(currNodeIndex / 2);
    
    while (this._container[parentNodeIndex] && newNode.priority > this._container[parentNodeIndex].priority) {
      const parent = this._container[parentNodeIndex];
      this._container[parentNodeIndex] = newNode;
      this._container[currNodeIndex] = parent;
      currNodeIndex = parentNodeIndex;
      parentNodeIndex = Math.floor(currNodeIndex / 2);
    }
  }

  /**
   * Removes and returns the top element in a heap 
   * (the element with most priority).
   * 
   * @returns {Boolean|Any} Returns false if a heap is
   * empty, otherwise the top element in a heap.
   * @example MaxHeap.insert('Cat', 1); // ['Cat']
   * MaxHeap.insert('Dog', 2); // ['Dog', 'Cat']
   * MaxHeap.insert('Fox', 3); // ['Fox', 'Dog', 'Cat']
   * MaxHeap.remove(); // ['Dog', 'Cat'] 
   * @memberOf MaxHeap
   */
  remove () {
    if (this._container.length < 3) { 
      const toReturn = this._container.pop();
      this._container[0] = null;
      if (toReturn !== null) {  
        return toReturn;
      }
      return false;
    }
    
    const toRemove = this._container[1];
    this._container[1] = this._container.pop();
    let currIndex = 1;
    let [left, right] = [2 * currIndex, 2 * currIndex + 1];
    let currChildIndex = this._container[right] && this._container[right].priority >= this._container[left].priority ? right : left;
    while (this._container[currChildIndex] && this._container[currIndex].priority <= this._container[currChildIndex].priority) {
      let currNode = this._container[currIndex];
      let currChildNode = this._container[currChildIndex];
      this._container[currChildIndex] = currNode;
      this._container[currIndex] = currChildNode;
    }
    return toRemove.element;
  }

  /**
   * Returns the top element in a heap.
   * 
   * @returns {Boolean|Any} Returns false if a heap is
   * empty, otherwise the top element in a heap.
   * @example MaxHeap.insert('Cat', 1); // ['Cat']
   * MaxHeap.insert('Dog', 2); // ['Dog', 'Cat']
   * MaxHeap.insert('Fox', 3); // ['Fox', 'Dog', 'Cat']
   * MaxHeap.peek(); // 'Fox', ['Fox', 'Dog', 'Cat']  
   * @memberOf MaxHeap
   */
  peek () {
    if (!this._container[1]) {
      return false;
    }
    return this._container[1].element;
  }

  /**
   * Checks if a heap is empty.
   * 
   * @returns {Boolean} Returns true if a heap is empty,
   * otherwise fasle.
   * @example MaxHeap.isEmpty(); // true
   * MaxHeap.insert('Cat', 1); // ['Cat']
   * MaxHeap.isEmpty(); // false 
   * @memberOf MaxHeap
   */
  isEmpty () {
    return this._container.length >= 2 ? false : true;
  }

  /**
   * Returns array representation of a heap.
   * 
   * @returns {Array} Returns array representation of a heap. 
   * @memberOf MaxHeap
   */
  toArray () {
    return this._container
      .filter(item => item === null ? false : true)
      .map(item => item.element);
  }
}

// Node function constructor 
// @private
function _Node(element, priority) { 
  this.element = element;
  this.priority = priority;
}

module.exports = MaxHeap;