binaryHeap.js

/** @class representing a binary heap node */
class Node {
  /**
   * @author: xenowits
   * @param {string} id The accountID of the user
   * @param {number} wt The associated weight (equal to noOfEntries)
   * @param {number} totalWt Total weight of the subheap headed by current Node
   */
  constructor(id, wt, totalWt) {
    this.accountID = id;
    this.wt = wt;
    this.totalWt = totalWt;
  }
}

/** @class representing a binary heap */
class BinaryHeap {
  /**
   * @author: xenowits
   * @param {number} heapSize Initial size of the heap
   */
  constructor(heapSize) {
    // keeping first element as undefined to make the heap 1-indexed
    this.heap = [undefined];
    this.heapSize = heapSize;
  }

  /**
   * Builds a heap from an array
   * Healthy tip: Shuffle the array before building a heap
   * 
   * @param {array} items Array of objects for building the heap
   */
  buildHeap(items) {
    items.forEach((ele) => {
      let node = new Node(ele.id, ele.wt, ele.wt);
      this.heap.push(node);
    });
    for (let i = this.heapSize; i > 1; i -= 1) {
      // Add total weight of child to parent
      this.heap[i >> 1].totalWt += this.heap[i].totalWt;
    }
    console.log(JSON.stringify(this.heap, null, 2));
  }

  /**
   * Pops a random node from the heap
   */
  popRandomNode() {
    // Let's start with a random value of gas
    var gas = this.heap[1].tw * Math.random();
    var i = 1;
    // Start driving at the root
    // While we have enough gas to go past node i
    while (gas > this.heap[i].wt) {
      // console.log("iteration on step:", i);
      gas -= this.heap[i].wt;
      i = i << 1;
      // Move to the first (left) child
      // If we have enough gas, drive past first child and descendants
      // And to the next child
      if (gas > this.heap[i].totalWt) {
        gas -= this.heap[i].totalWt;
        i += 1;
      }
    }
    // So heap[i] is our selected node
    var accountID = this.heap[i].accountID;
    console.log("Winner is ", accountID, " who has weight ", this.heap[i].wt);
    var delta = this.heap[this.heapSize].wt - this.heap[i].wt;

    // To make sure heap[i] is never chosen again,
    // exchange last element of heap with heap[i]
    this.heap[i].accountID = this.heap[this.heapSize].accountID;
    this.heap[i].wt = this.heap[this.heapSize].wt;
    this.heapSize -= 1;

    // Also, propagate the new change up to the root
    while (i > 0) {
        this.heap[i].totalWt += delta;
        i = i >> 1;
    }

    return accountID;
  }
}

module.exports = BinaryHeap;