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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Largest Element Extraction

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

DSA Javascript

class MaxHeap {
  constructor() {
    this.heap = [];
  }
  insert(val) {
    this.heap.push(val);
    this.bubbleUp();
  }
  bubbleUp() {
    let idx = this.heap.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[parentIdx] >= this.heap[idx]) break;
      [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
      idx = parentIdx;
    }
  }
  extractMax() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown();
    }
    return max;
  }
  sinkDown() {
    let idx = 0;
    const length = this.heap.length;
    const element = this.heap[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;
      if (leftChildIdx < length) {
        leftChild = this.heap[leftChildIdx];
        if (leftChild > element) swap = leftChildIdx;
      }
      if (rightChildIdx < length) {
        rightChild = this.heap[rightChildIdx];
        if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {
          swap = rightChildIdx;
        }
      }
      if (swap === null) break;
      [this.heap[idx], this.heap[swap]] = [this.heap[swap], this.heap[idx]];
      idx = swap;
    }
  }
}

function findKthLargest(nums, k) {
  const maxHeap = new MaxHeap();
  for (const num of nums) {
    maxHeap.insert(num);
  }
  let kthLargest = null;
  for (let i = 0; i < k; i++) {
    kthLargest = maxHeap.extractMax();
  }
  return kthLargest;
}

const nums = [3, 2, 1, 5, 6, 4];
const k = 3;
console.log(findKthLargest(nums, k));

A 6

B 3

C 5

D 4

💡 Hint

Remember the max heap always extracts the largest element first.

The max heap extracts elements in descending order: 6, 5, then 4. The 3rd largest element is 4.

🧠 Conceptual

intermediate

Understanding Max Heap Property

Which statement best describes the max heap property used in finding the kth largest element?

A Every parent node is smaller than its children.

B Every parent node is equal to its children.

C Every parent node is greater than or equal to its children.

D The heap is sorted in ascending order.

💡 Hint

Think about what makes the root the largest element.

In a max heap, each parent node is greater than or equal to its children, ensuring the largest element is at the root.

🔧 Debug

advanced

Identify the Error in Max Heap Extraction

What error will occur when running this code snippet for extracting max from a max heap?

DSA Javascript

extractMax() {
  if (this.heap.length === 0) return null;
  const max = this.heap[0];
  const end = this.heap.pop();
  this.heap[0] = end;
  this.sinkDown();
  return max;
}

A No error, works correctly

B Runtime error when heap is empty after pop

C TypeError because sinkDown is not defined

D ReferenceError because max is not declared

💡 Hint

Consider what happens when the heap has only one element.

If the heap has one element, pop removes it leaving an empty array. Assigning this.heap[0] = end sets undefined, then sinkDown runs on empty heap causing errors.

🚀 Application

advanced

Resulting Heap After Insertions

After inserting the numbers [10, 4, 15, 20, 0] into an empty max heap, what is the heap array?

A [20, 15, 10, 4, 0]

B [15, 20, 10, 4, 0]

C [20, 10, 15, 4, 0]

D [10, 20, 15, 4, 0]

💡 Hint

Remember the max heap property after each insertion.

Inserting 10, 4, 15, 20, 0 results in a max heap with 20 at root, then 15 and 10 as children, followed by 4 and 0.

❓ Predict Output

expert

Output of Kth Largest Element with Duplicate Values

What is the output of the following code that finds the 4th largest element in an array with duplicates using a max heap?

DSA Javascript

class MaxHeap {
  constructor() {
    this.heap = [];
  }
  insert(val) {
    this.heap.push(val);
    this.bubbleUp();
  }
  bubbleUp() {
    let idx = this.heap.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[parentIdx] >= this.heap[idx]) break;
      [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
      idx = parentIdx;
    }
  }
  extractMax() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown();
    }
    return max;
  }
  sinkDown() {
    let idx = 0;
    const length = this.heap.length;
    const element = this.heap[0];
    while (true) {
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;
      if (leftChildIdx < length) {
        leftChild = this.heap[leftChildIdx];
        if (leftChild > element) swap = leftChildIdx;
      }
      if (rightChildIdx < length) {
        rightChild = this.heap[rightChildIdx];
        if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {
          swap = rightChildIdx;
        }
      }
      if (swap === null) break;
      [this.heap[idx], this.heap[swap]] = [this.heap[swap], this.heap[idx]];
      idx = swap;
    }
  }
}

function findKthLargest(nums, k) {
  const maxHeap = new MaxHeap();
  for (const num of nums) {
    maxHeap.insert(num);
  }
  let kthLargest = null;
  for (let i = 0; i < k; i++) {
    kthLargest = maxHeap.extractMax();
  }
  return kthLargest;
}

const nums = [5, 3, 1, 5, 6, 4, 6];
const k = 4;
console.log(findKthLargest(nums, k));

A 5

B 4

C 3

D 6

💡 Hint

Duplicates affect the order but max heap extracts largest each time.

The max heap extracts in order: 6, 6, 5, 5. The 4th largest element is 5.