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.

Practice

1. What is the main idea behind finding the kth largest element using a max heap?

easy

A. Build a max heap from the array and extract the max element k times

B. Sort the array and pick the kth element from the start

C. Use a min heap to store all elements and pop k times

D. Reverse the array and pick the kth element

Solution

1. Step 1: Understand max heap property

   A max heap always keeps the largest element at the root, so extracting the root gives the largest element.

2. Step 2: Extract max k times to get the kth largest

   By removing the root k times, the last extracted element is the kth largest.

3. Final Answer:

   Build max heap and extract max k times -> Option A

4. Quick Check:

   Max heap extraction = kth largest element [OK]

Hint: Extract max from max heap k times to find kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Sorting and picking wrong index
• Extracting fewer or more than k times

2. Which of the following is the correct way to create a max heap from an array arr in JavaScript using a custom heap class?

easy

A. const maxHeap = new MaxHeap(arr); maxHeap.heapify();

B. const maxHeap = new MaxHeap(); maxHeap.insert(arr);

C. const maxHeap = new MaxHeap(); maxHeap.build(arr);

D. const maxHeap = new MaxHeap(arr); maxHeap.buildHeap();

Solution

1. Step 1: Recognize typical max heap initialization

   Usually, a max heap class accepts an array and has a method like buildHeap() to create the heap structure.

2. Step 2: Identify correct method call

   buildHeap() is the standard method to convert the array into a max heap, so calling it after initialization is correct.

3. Final Answer:

   const maxHeap = new MaxHeap(arr); maxHeap.buildHeap(); -> Option D

4. Quick Check:

   buildHeap() builds max heap from array [OK]

Hint: Use buildHeap() after passing array to MaxHeap constructor [OK]

Common Mistakes:

• Calling insert with whole array instead of single elements
• Using wrong method names like heapify or build
• Not calling any method to build the heap

3. What will be the output of the following code snippet?

class MaxHeap {
  constructor(arr) {
    this.heap = arr;
    this.buildHeap();
  }
  buildHeap() {
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.heapify(i);
    }
  }
  heapify(i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
    if (right < this.heap.length && this.heap[right] > this.heap[largest]) largest = right;
    if (largest !== i) {
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      this.heapify(largest);
    }
  }
  extractMax() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapify(0);
    return max;
  }
}

const arr = [3, 2, 1, 5, 6, 4];
const maxHeap = new MaxHeap(arr);
let kthLargest;
for (let i = 0; i < 2; i++) {
  kthLargest = maxHeap.extractMax();
}
console.log(kthLargest);

medium

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Build max heap from array

   Array [3,2,1,5,6,4] becomes max heap with root 6 after buildHeap.

2. Step 2: Extract max twice

   First extractMax returns 6, second extractMax returns 5, so kthLargest after loop is 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   2nd largest element = 5 [OK]

Hint: Extract max twice from max heap to get 2nd largest [OK]

Common Mistakes:

• Assuming heap root changes incorrectly after extraction
• Confusing 1st largest with 2nd largest
• Not updating heap after extraction

4. Identify the bug in the following code that tries to find the 3rd largest element using a max heap:

class MaxHeap {
  constructor(arr) {
    this.heap = arr;
    this.buildHeap();
  }
  buildHeap() {
    for (let i = 0; i < this.heap.length / 2; i++) {
      this.heapify(i);
    }
  }
  heapify(i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
    if (right < this.heap.length && this.heap[right] > this.heap[largest]) largest = right;
    if (largest !== i) {
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      this.heapify(largest);
    }
  }
  extractMax() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapify(0);
    return max;
  }
}

const arr = [7, 10, 4, 3, 20, 15];
const maxHeap = new MaxHeap(arr);
let kthLargest;
for (let i = 0; i < 3; i++) {
  kthLargest = maxHeap.extractMax();
}
console.log(kthLargest);

medium

A. The buildHeap loop should run backwards from middle to 0

B. extractMax should not call heapify after popping

C. heapify should swap with smallest child instead of largest

D. The array should be sorted before building the heap

Solution

1. Step 1: Analyze buildHeap loop direction

   Heap building requires heapify calls from last parent to root, so loop must run backwards from middle to 0.

2. Step 2: Identify incorrect loop direction

   Current loop runs forwards, which does not correctly heapify the tree, causing incorrect heap structure.

3. Final Answer:

   The buildHeap loop should run backwards from middle to 0 -> Option A

4. Quick Check:

   buildHeap loop direction = backwards [OK]

Hint: buildHeap loop must run backwards from middle to root [OK]

Common Mistakes:

• Running buildHeap loop forwards
• Not calling heapify after extractMax
• Swapping with wrong child in heapify

5. Given an array arr = [12, 3, 5, 7, 19, 0, 4], write a JavaScript function using a max heap to find the 4th largest element. What is the output of your function?

hard

A. 4

B. 5

C. 7

D. 3

Solution

1. Step 1: Build max heap from array

   Array becomes max heap with root 19 after heapify.

2. Step 2: Extract max 4 times

   Extracted elements in order: 19, 12, 7, 5. The 4th largest is 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   4th largest element = 7 [OK]

Hint: Extract max k times; last extracted is kth largest [OK]

Common Mistakes:

• Extracting fewer times than k
• Confusing 3rd largest with 4th largest
• Not rebuilding heap after extraction