Kth Smallest Element Using Min Heap in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

What is the output of the following code that finds the 3rd smallest element using a min heap?

DSA Python

import heapq
arr = [7, 10, 4, 3, 20, 15]
k = 3
heapq.heapify(arr)
result = None
for _ in range(k):
    result = heapq.heappop(arr)
print(result)

A 10

B 4

C 7

D 3

💡 Hint

Remember that heapq.heapify creates a min heap and heappop removes the smallest element each time.

The min heap after heapify is [3, 7, 4, 10, 20, 15]. Popping three times removes 3, then 4, then 7. So the 3rd smallest element is 7.

🧠 Conceptual

intermediate

Understanding Min Heap Property

Which statement best describes the min heap property used to find the kth smallest element?

A The root is always the largest element in the heap.

B Every parent node is smaller than or equal to its children.

C The heap is always sorted in ascending order.

D The heap stores elements in the order they were inserted.

💡 Hint

Think about how the smallest element is always accessible in a min heap.

In a min heap, each parent node is smaller than or equal to its children, ensuring the smallest element is at the root.

🔧 Debug

advanced

Identify the Error in Kth Smallest Element Code

What error will this code produce when trying to find the 4th smallest element?

DSA Python

import heapq
arr = [5, 3, 8]
k = 4
heapq.heapify(arr)
for _ in range(k):
    print(heapq.heappop(arr))

A KeyError

B No error, prints all elements

C IndexError

D IndexError: pop from an empty heap

💡 Hint

Check what happens when you pop more elements than exist in the heap.

The heap has only 3 elements but the code tries to pop 4 times, causing an IndexError: pop from an empty heap.

🚀 Application

advanced

Resulting Heap After Extracting Kth Smallest

After extracting the 2nd smallest element from the min heap built from [12, 3, 5, 7, 19], what is the state of the heap?

DSA Python

import heapq
arr = [12, 3, 5, 7, 19]
heapq.heapify(arr)
heapq.heappop(arr)
heapq.heappop(arr)
print(arr)

A [7, 12, 19]

B [5, 7, 12, 19]

C [3, 5, 7, 12, 19]

D [12, 7, 19]

💡 Hint

Remember that after popping, the heap restructures to maintain the min heap property.

After popping 3 and 5, the remaining heap elements are [7, 12, 19] maintaining the min heap property.

❓ Predict Output

expert

Output of Kth Smallest Element with Duplicate Values

What is the output of this code finding the 4th smallest element in an array with duplicates?

DSA Python

import heapq
arr = [2, 1, 2, 1, 3]
k = 4
heapq.heapify(arr)
result = None
for _ in range(k):
    result = heapq.heappop(arr)
print(result)

A 2

B 3

C null

D 1

💡 Hint

Duplicates are treated as separate elements in the heap.

The sorted order is [1, 1, 2, 2, 3]. The 4th smallest element is the second 2.

Practice

1. What does a min heap help you find efficiently when searching for the kth smallest element in a list?

easy

A. The smallest elements in ascending order

B. The largest elements in descending order

C. The middle element only

D. The sum of all elements

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the root, so it helps access the smallest values quickly.

2. Step 2: Use min heap to find kth smallest

   By extracting the root k times, we get the kth smallest element efficiently.

3. Final Answer:

   The smallest elements in ascending order -> Option A

4. Quick Check:

   Min heap = smallest elements first [OK]

Hint: Min heap root is always the smallest element [OK]

Common Mistakes:

• Confusing min heap with max heap
• Thinking min heap sorts all elements fully
• Assuming kth largest instead of kth smallest

2. Which of the following Python code snippets correctly creates a min heap from a list arr?

easy

A. import heapq
heapq.heapSort(arr)

B. import heapq
heapq.minHeap(arr)

C. import heapq
heapq.makeheap(arr)

D. import heapq
heapq.heapify(arr)

Solution

1. Step 1: Recall Python heapq functions

   The correct function to convert a list into a min heap is heapq.heapify().

2. Step 2: Check other options

   Functions like heapSort, makeheap, and minHeap do not exist in the heapq module.

3. Final Answer:

   import heapq heapq.heapify(arr) -> Option D

4. Quick Check:

   heapq.heapify = min heap creation [OK]

Hint: Use heapq.heapify() to build a min heap from list [OK]

Common Mistakes:

• Using non-existent heapq functions
• Trying to sort with heapq.heapify
• Confusing heapify with sorted

3. What is the output of the following code?

import heapq
arr = [7, 10, 4, 3, 20, 15]
heapq.heapify(arr)
k = 3
for _ in range(k-1):
    heapq.heappop(arr)
print(arr[0])

medium

A. 7

B. 10

C. 15

D. 20

Solution

1. Step 1: Build min heap from arr

   After heapify, arr becomes a min heap: [3, 7, 4, 10, 20, 15].

2. Step 2: Pop smallest elements k-1 times

   Pop 1st: removes 3, heap adjusts to [4, 7, 15, 10, 20]. Now root is 4.
   Pop 2nd: removes 4, heap adjusts to [7, 10, 15, 20]. Now root is 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   3rd smallest element = 7 [OK]

Hint: Pop k-1 times, then peek root for kth smallest [OK]

Common Mistakes:

• Not popping k-1 times before checking root
• Assuming original array order
• Confusing min heap root after pops

4. Find the error in this code to get the kth smallest element using a min heap:

import heapq
arr = [5, 3, 8, 6, 2]
heapq.heapify(arr)
k = 2
for i in range(k):
    heapq.heappop(arr)
print(arr[0])

medium

A. Print statement should be inside the loop

B. Loop should run k-1 times, not k times

C. Use max heap instead of min heap

D. heapq.heapify() is missing

Solution

1. Step 1: Understand kth smallest extraction

   To get the kth smallest, pop the smallest element k-1 times, then peek the root.

2. Step 2: Identify loop error

   The loop runs k times, popping k elements, so the root after loop is (k+1)th smallest, which is wrong.

3. Final Answer:

   Loop should run k-1 times, not k times -> Option B

4. Quick Check:

   Pop k-1 times, then peek root [OK]

Hint: Pop k-1 times before checking root for kth smallest [OK]

Common Mistakes:

• Popping k times instead of k-1
• Forgetting to heapify before popping
• Using max heap instead of min heap

5. Given two sorted arrays A = [1, 3, 5] and B = [2, 4, 6], how can you find the 4th smallest element using a min heap approach?

hard

A. Heapify only array B and pop 4 times

B. Heapify only array A and pop 4 times

C. Merge both arrays, heapify, then pop 3 times and peek root

D. Sort both arrays and pick the 4th element directly

Solution

1. Step 1: Combine arrays for global order

   To find the 4th smallest overall, combine both arrays into one list.

2. Step 2: Use min heap to find kth smallest

   Heapify the combined list, pop 3 times (k-1), then peek root for 4th smallest.

3. Final Answer:

   Merge both arrays, heapify, then pop 3 times and peek root -> Option C

4. Quick Check:

   Combine + heapify + pop k-1 times [OK]

Hint: Combine arrays before heapify for kth smallest [OK]

Common Mistakes:

• Heapifying only one array
• Assuming arrays are merged automatically
• Using sorting instead of heap approach