Kth Largest Element Using Max Heap in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of extracting the 3rd largest element using a max heap

What is the output of the following TypeScript code that finds the 3rd largest element using a max heap?

DSA Typescript

class MaxHeap {
  heap: number[] = [];

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMax(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.sinkDown(0);
    return max;
  }

  sinkDown(index: number) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swapIdx: number | null = null;

      if (leftChildIdx < length) {
        if (this.heap[leftChildIdx] > element) {
          swapIdx = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        if (
          (swapIdx === null && this.heap[rightChildIdx] > element) ||
          (swapIdx !== null && this.heap[rightChildIdx] > this.heap[leftChildIdx])
        ) {
          swapIdx = rightChildIdx;
        }
      }
      if (swapIdx === null) break;
      [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
      index = swapIdx;
    }
  }
}

const nums = [7, 10, 4, 3, 20, 15];
const k = 3;
const maxHeap = new MaxHeap();
for (const num of nums) {
  maxHeap.insert(num);
}
let kthLargest: number | undefined;
for (let i = 0; i < k; i++) {
  kthLargest = maxHeap.extractMax();
}
console.log(kthLargest);

A 7

B 15

C 10

D 20

💡 Hint

Remember that the max heap always extracts the largest element first. Extract k times to get the kth largest.

The max heap inserts all numbers. Extracting max 3 times gives: 20 (1st), 15 (2nd), 10 (3rd). The last extracted value is 10, which is printed. Option C.

❓ Predict Output

intermediate

Output after building max heap and extracting max once

What is the state of the heap array after inserting [5, 3, 8, 4] and extracting the max once?

DSA Typescript

class MaxHeap {
  heap: number[] = [];

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMax(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.sinkDown(0);
    return max;
  }

  sinkDown(index: number) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swapIdx: number | null = null;

      if (leftChildIdx < length) {
        if (this.heap[leftChildIdx] > element) {
          swapIdx = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        if (
          (swapIdx === null && this.heap[rightChildIdx] > element) ||
          (swapIdx !== null && this.heap[rightChildIdx] > this.heap[leftChildIdx])
        ) {
          swapIdx = rightChildIdx;
        }
      }
      if (swapIdx === null) break;
      [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
      index = swapIdx;
    }
  }
}

const maxHeap = new MaxHeap();
[5, 3, 8, 4].forEach(n => maxHeap.insert(n));
maxHeap.extractMax();
console.log(maxHeap.heap);

A [5, 4, 3]

B [8, 5, 3, 4]

C [5, 4, 3, 8]

D [4, 5, 3]

💡 Hint

After extracting max, the heap reorders to maintain max heap property.

Initial heap after inserts is [8, 4, 5, 3]. Extract max removes 8, replaces root with 3 (last), then sinks down: swaps with larger child 5 at index 2, resulting in [5, 4, 3].

🔧 Debug

advanced

Identify the error in max heap sinkDown method

What error will occur when running this sinkDown method in a max heap implementation?

DSA Typescript

sinkDown(index: number) {
  const length = this.heap.length;
  const element = this.heap[index];
  while (true) {
    let leftChildIdx = 2 * index + 1;
    let rightChildIdx = 2 * index + 2;
    let swapIdx: number | null = null;

    if (leftChildIdx < length) {
      if (this.heap[leftChildIdx] < element) {
        swapIdx = leftChildIdx;
      }
    }
    if (rightChildIdx < length) {
      if (
        (swapIdx === null && this.heap[rightChildIdx] < element) ||
        (swapIdx !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])
      ) {
        swapIdx = rightChildIdx;
      }
    }
    if (swapIdx === null) break;
    [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
    index = swapIdx;
  }
}

A The sinkDown will incorrectly swap smaller children, breaking max heap property

B The code will cause an infinite loop because swapIdx is never updated

C The code will throw a TypeError due to undefined heap elements

D No error; the sinkDown method works correctly

💡 Hint

Check the comparison operators used for deciding swaps in a max heap.

The sinkDown method uses '<' comparisons, which is for min heap. For max heap, it should use '>' to swap with larger children. Using '<' causes the heap to swap with smaller children, breaking max heap property.

🚀 Application

advanced

Find the 2nd largest element using max heap

Given the array [12, 3, 5, 7, 19], what is the 2nd largest element found by extracting max twice from a max heap?

DSA Typescript

class MaxHeap {
  heap: number[] = [];

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] >= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMax(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.sinkDown(0);
    return max;
  }

  sinkDown(index: number) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swapIdx: number | null = null;

      if (leftChildIdx < length) {
        if (this.heap[leftChildIdx] > element) {
          swapIdx = leftChildIdx;
        }
      }
      if (rightChildIdx < length) {
        if (
          (swapIdx === null && this.heap[rightChildIdx] > element) ||
          (swapIdx !== null && this.heap[rightChildIdx] > this.heap[leftChildIdx])
        ) {
          swapIdx = rightChildIdx;
        }
      }
      if (swapIdx === null) break;
      [this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
      index = swapIdx;
    }
  }
}

const nums = [12, 3, 5, 7, 19];
const maxHeap = new MaxHeap();
for (const num of nums) {
  maxHeap.insert(num);
}
maxHeap.extractMax();
const secondLargest = maxHeap.extractMax();
console.log(secondLargest);

A 19

B 12

C 7

D 5

💡 Hint

Extract max twice; the first extraction removes the largest, the second is the 2nd largest.

The largest element is 19, extracted first. The next largest is 12, extracted second. So output is 12.

🧠 Conceptual

expert

Time complexity of finding kth largest element using max heap

What is the time complexity of finding the kth largest element in an unsorted array of size n by building a max heap and extracting max k times?

A O(nk)

B O(n log n + k)

C O(k log n)

D O(n + k log n)

💡 Hint

Building a max heap from n elements takes O(n). Each extraction takes O(log n).

Building the max heap is O(n). Extracting max k times costs O(k log n). Total is O(n + k log n).