text: /*
  Kth Largest In A Stream
  Given an initial list along with another list of numbers to be appended with the initial list and an integer K, return an array consisting of the Kth largest element after adding each element from the first list to the second list.
  Example
  Input: [ 2, [4, 6], [5, 2, 20] ]
  Output: [5, 5, 6]
  
  Append Stream            Sorted Stream   2nd largest
  5   [4, 6, 5]              [4, 5, 6]             5
  2  [4, 6, 5, 2]            [2, 4, 5, 6]          5
  20 [4, 6, 5, 2, 20]        [2, 4, 5, 6, 20]      6
  */
  
  // brute force: time: O(|append_stream| * (|append_stream| + |initial_stream|) * log(|append_stream| + |initial_stream|)).
  // brute force: aux space: O(append_stream)
  
  class MinHeap {
    constructor(array) {
      this.heap = this.buildHeap(array);
    }
  
    buildHeap(array) {
      const firstParentIdx = Math.floor((array.length - 2) / 2);
      for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
        this.siftDown(currentIdx, array.length - 1, array);
      }
      return array;
    }
  
    siftDown(currentIdx, endIdx, heap) {
      let childOneIdx = currentIdx * 2 + 1;
      while (childOneIdx <= endIdx) {
        const childTwoIdx =
          currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
        let idxToSwap;
  
        if (childTwoIdx !== -1 && heap[childTwoIdx] < heap[childOneIdx]) {
          idxToSwap = childTwoIdx;
        } else {
          idxToSwap = childOneIdx;
        }
        if (heap[idxToSwap] < heap[currentIdx]) {
          this.swap(currentIdx, idxToSwap, heap);
          currentIdx = idxToSwap;
          childOneIdx = currentIdx * 2 + 1;
        } else {
          return;
        }
      }
    }
  
    siftUp(currentIdx, heap) {
      let parentIdx = Math.floor((currentIdx - 1) / 2);
      while (currentIdx > 0 && heap[currentIdx] < heap[parentIdx]) {
        this.swap(currentIdx, parentIdx, heap);
        currentIdx = parentIdx;
        parentIdx = Math.floor((currentIdx - 1) / 2);
      }
    }
  
    peek() {
      return this.heap[0];
    }
    remove() {
      this.swap(0, this.heap.length - 1, this.heap);
      const valueToRemove = this.heap.pop();
      this.siftDown(0, this.heap.length - 1, this.heap);
      return valueToRemove;
    }
  
    insert(value) {
      this.heap.push(value);
      this.siftUp(this.heap.length - 1, this.heap);
    }
  
    swap(i, j, heap) {
      const temp = heap[j];
      heap[j] = heap[i];
      heap[i] = temp;
    }
  }
  // heap solution: time O(n log(k)) | aux space: O(k)
  function kth_largest(k, initial_stream, append_stream) {
    let min_heap = new MinHeap([]);
    for (let i = 0; i < initial_stream.length; i++) {
      min_heap.insert(initial_stream[i]);
  
      //make sure heap size does not eceed k
      if (min_heap.length > k) {
        min_heap.remove(); // remove the element smaller than the k largest elements
      }
    }
    console.log({ min_heap });
    let result = [];
    for (let i = 0; i < append_stream.length; i++) {
      min_heap.insert(append_stream[i]);
  
      // make sure that the heap size does not exceed k
      if (min_heap.length > k) {
        min_heap.remove(); // remove the element smaller than the k largest elements
        console.log(min_heap);
        // adding current kth largest element
        result.push(min_heap.peek());
      }
    }
    return result;
  }
  
  console.log(kth_largest(2, [4, 6], [5, 2, 20]));
  