Find maximum possible capital

1-find-maximum-capital.js

// c is my capital
// k is times I want to invest
// capitals is list of min capitals of projects to invest
// profits is how much profit a project brings
export function maximumCapital(c, k, capitals, profits) {
  // in this heap we are going to store capitals that
  // are required by projects to invest into them
  // top element is always the cheapest project to invest to
  const capHeap = new TupleHeap();

  // in this heap we're going to store profits of projects
  // that we can afford to invest to
  // so project is either present in the capitals heap (above)
  // or in this profits heap, but not both
  const profitHeap = new TupleHeap();

  // push capitals required by projects to heap
  capitals.forEach((cap, index) => capHeap.push([cap, index]));

  // hold our total capital in a variable
  // we will be adding profits of projects here
  let myCap = c;

  // hold how many times we've invested
  // we stop investing when count reaches k
  let count = 0;

  // invest in project no more than k times
  // if there are no projects to invest, but count < k,
  // we just increment count
  while (count < k) {
    while (capHeap.length() > 0) {
      // look at the smallest project capital to invest (heap top)
      const [cap, index] = capHeap.peekTop();
      if (cap > myCap) {
        // if we can't invest into the cheapest project,
        // means we cannot invest in any other project,
        // since all other projects are more expensive
        break;
      }
      // remove the smallest project capital from the heap
      // the second smallest will take its place
      capHeap.deleteTop();
      // push the project profit into the profits heap
      // we make the value negative so we dont need to implement
      // a separate max heap
      profitHeap.push([-profits[index], index]);
    }
    // at this point we've removed all projects that we can afford
    // from the capitals heap,
    // and added their profits to the profits heap
    // now we need to pick the top element from the profits heap
    // this will be the project that brings the most profit
    // out of all projects that we can afford at this step
    if (profitHeap.length() > 0) {
      const [profit] = profitHeap.deleteTop();
      // increase our total capital by adding the projects profit
      myCap = myCap - profit;
      // at this point our total capital is increased,
      // and on the next iteration we might afford more projects
      // from the capitals heap
    }
    // at this point we've either invested in a project,
    // or there were no projects we can afford to invest to,
    // increase our count anyway
    count += 1;
  }

  return myCap;
}

2-Heap.js

class Heap {
  heap = [];

  getValue(index) {
    return this.heap[index];
  }

  getParentIndex(i) {
    return Math.floor(i / 2);
  }

  getLeftChildIndex(i) {
    return i * 2 + 1;
  }

  getRightChildIndex(i) {
    return i * 2 + 2;
  }

  deleteTop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length === 0) {
      return top;
    }
    this.heap[0] = last;
    this.bubbleDown(0);
    return top;
  }

  peekTop() {
    return this.heap[0];
  }

  bubbleUp(index) {
    if (index === 0) {
      return;
    }

    const value = this.getValue(index);

    const parentIndex = this.getParentIndex(index);
    const parent = this.getValue(parentIndex);

    if (value < parent) {
      const parent = this.heap[parentIndex];
      this.heap[parentIndex] = this.heap[index];
      this.heap[index] = parent;
      this.bubbleUp(parentIndex);
    }
  }

  bubbleDown(index) {
    const value = this.getValue(index);

    const leftChildIndex = this.getLeftChildIndex(index);
    const rightChildIndex = this.getRightChildIndex(index);

    const leftChild = this.getValue(leftChildIndex);
    const rightChild = this.getValue(rightChildIndex);

    const lInf = leftChild ?? Infinity;
    const rInf = rightChild ?? Infinity;

    // if min heap property is satisified, nothing to do
    // each child is greater than parent
    if (lInf > value && rInf > value) {
      return;
    }

    // min heap prop is not satisfied, swap with smallest child
    const smallestChildIndex = lInf <= rInf ? leftChildIndex : rightChildIndex;

    const child = this.heap[smallestChildIndex];
    this.heap[smallestChildIndex] = this.heap[index];
    this.heap[index] = child;
    this.bubbleDown(smallestChildIndex);
  }

  getHeap() {
    return this.heap;
  }

  push(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }

  print() {
    console.log("print:");
    this.heap.forEach((item, index) => {
      const children = [
        this.heap[this.getLeftChildIndex(index)],
        this.heap[this.getRightChildIndex(index)],
      ];
      if (children.filter(Boolean).length > 0 || index === 0) {
        console.log("node", item, "children", children, "index", index);
      }
    });
  }

  length() {
    return this.heap.length;
  }
}

3-TupleHeap.js

class TupleHeap extends Heap {
  getValue(index) {
    return this.heap[index] ? this.heap[index][0] : null;
  }
}

4-README.md