educative.io

Time Complexity K * Log K using Max Heap (Just for fun)

Courses
,
#1

If you were thinking if you can use Max Heap or not.
Below is the implementation

import * as assert from 'assert';
const { MaxHeap } = require('@datastructures-js/max-heap');
const { MinHeap } = require('@datastructures-js/min-heap');

/**
 *
 * @param lists
 * @param processedIndices
 * returns next values from each array
 */
const nextValuesFromEachList = (lists: Array<Array<number>>, processedIndices: any): any => {
  const minHeap = new MinHeap();
  lists.forEach((list, index) => {
    if (processedIndices[index] < processedIndices[`${index}-length`]) {
      minHeap.insert(list[processedIndices[index] + 1], { listIndex: index}) // next value in the list
    }
  })
  return minHeap;
}

/**
 *
 * @param lists
 * @param k
 * returns kth smallest number using max heap
 * the HARD way
 */
const kThSmallestNumberViaMaxHeap = (lists: Array<Array<number>>, k: number): number => {
  const maxHeap = new MaxHeap();
  const processedIndices: any = {};
  lists.forEach((list, index) => {
    maxHeap.insert(list[0], {});
    processedIndices[index] = 0;
    processedIndices[`${index}-length`] = list.length;
  });

  while(maxHeap.size() < k) {
    const nextValues = nextValuesFromEachList(lists, processedIndices);
    if (nextValues.length === 0) {
      return -1;
    }
    const nextMin = nextValues.root();
    // we are gooing to insert this and increment the in hash value
    processedIndices[nextMin.value.listIndex] += 1;
    maxHeap.insert(nextMin.key, {});
  }
  const kThSmallest = maxHeap.root().key; // the one at top will be kth largest
  return kThSmallest;
  // Time complexity: Terrible
}

Cheers