Basic algorithms in JS

algorithms.js

// GCD
// Euclidean algorithm
const gcd = (a,b) => {
    if(!b) return a;
    return gcd(b, a%b);
}

// LCM
// USING GCD
const lcm = (a,b) =>{
    return (a*b)/gcd(a,b);
}

// Power Set
// Bitwise Solution
const powerSet = (arr) => {
  const number = 2 ** arr.length;
  const subsets = [];

  for (let combIndex = 0; combIndex < number; combIndex++) {
    const subset = [];
    for (let elIndex = 0; elIndex < arr.length; elIndex++) {
      if (combIndex & (1 << elIndex)) {
        subset.push(arr[elIndex]);
      }
    }
    subsets.push(subset);
  }
  return subsets;
};
// BackTracking Recursive
function btPowerSetRecursive(originalSet, allSubsets = [[]], currentSubSet = [], startAt = 0){
  for (let position = startAt; position < originalSet.length; position += 1) {
    currentSubSet.push(originalSet[position]);

    allSubsets.push([...currentSubSet]);
    
    btPowerSetRecursive(originalSet, allSubsets, currentSubSet, position + 1);

    currentSubSet.pop();
  }
  return allSubsets;
}

// Binary Search
// sorted array, target to find
// O(log n)
const binarySearch = (arr, target) => {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = left + ~~((right - left) * 0.5);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; //not found
};


// Min Heap, Priority Queue
class Heap {
  constructor() {
    this.heap = [];
  }

  getLeftChildIndex = parentIndex => parentIndex * 2 + 1;

  getRightChildIndex = parentIndex => parentIndex * 2 + 2;

  getParentIndex = childIndex => Math.floor((childIndex - 1) / 2);

  peek = () => this.heap[0];

  insert = (key, value) => {
    let node = { key, value };
    this.heap.push(node);
    this.heapifyUp();
  };

  heapifyUp = () => {
    let index = this.heap.length - 1;
    const lastInsertedNode = this.heap[index];

    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      if (this.heap[parentIndex].key > lastInsertedNode.key) {
        this.heap[index] = this.heap[parentIndex];
        index = parentIndex;
      } else {
        break;
      }
    }

    this.heap[index] = lastInsertedNode;
  };

  remove = () => {
    const count = this.heap.length;
    const rootNode = this.peek();

    if (count <= 0) return undefined;
    else if (count === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    return rootNode;
  };

  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const rootNode = this.peek();

    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      const smallerChildIndex =
        rightChildIndex < count &&
        this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
          ? rightChildIndex
          : leftChildIndex;

      if (this.heap[smallerChildIndex].key <= rootNode.key) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }

    this.heap[index] = rootNode;
  };
}

class PriorityQueue extends Heap {
  constructor() {
    super();
  }

  enqueue = (priority, value) => this.insert(priority, value);
  dequeue = () => this.remove();
  isEmpty = () => this.heap.length <= 0;
}