Kth Smallest Element Using Min Heap in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Min Heap?

A Min Heap is a special tree-based data structure where the parent node is always smaller than or equal to its child nodes. This means the smallest element is always at the root.

beginner

How does a Min Heap help find the kth smallest element?

By building a Min Heap from the array, the smallest element is at the root. Extracting the root k times gives the kth smallest element.

intermediate

What is the time complexity of finding the kth smallest element using a Min Heap?

Building the Min Heap takes O(n) time, and extracting the minimum k times takes O(k log n), so total time complexity is O(n + k log n).

intermediate

What happens during the 'extract min' operation in a Min Heap?

The root (smallest element) is removed, the last element moves to the root, and then the heap is adjusted (heapify) to maintain the Min Heap property.

intermediate

Why is a Min Heap preferred over sorting the entire array to find the kth smallest element?

Using a Min Heap can be more efficient because it avoids sorting the entire array, especially when k is small compared to n, reducing unnecessary work.

What is the root of a Min Heap always?

A Any random element

B The smallest element

C The middle element

D The largest element

In a Min Heap, the root is always the smallest element.

How many times do you extract the minimum element to find the kth smallest element using a Min Heap?

A k times

B n times

C 1 time

D k/2 times

You extract the minimum element k times to reach the kth smallest element.

What is the time complexity to build a Min Heap from an array of size n?

A O(n log n)

B O(k log n)

C O(log n)

D O(n)

Building a Min Heap from an array takes O(n) time.

Which operation maintains the Min Heap property after removing the root?

A Heapify

B Sort

C Insert

D Swap

Heapify adjusts the heap to maintain the Min Heap property after removal.

If k is very small compared to n, which method is more efficient to find the kth smallest element?

A Linear search

B Sorting the entire array

C Using a Min Heap

D Binary search

Using a Min Heap is more efficient when k is small because it avoids full sorting.

Explain step-by-step how to find the kth smallest element using a Min Heap.

Think about how the smallest element is always at the root and how removing it repeatedly helps.

Describe the time complexity of the kth smallest element algorithm using a Min Heap and why.

Consider the cost of building the heap and the cost of each extraction.

Practice

1. What is the main idea behind finding the kth smallest element using a min heap?

easy

A. Sort the array and pick the element at index k

B. Build a min heap from the array and extract the minimum element k times

C. Build a max heap and extract the maximum element k times

D. Use a hash map to count frequencies and find the kth smallest

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the root, so extracting the root gives the smallest element.

2. Step 2: Extract minimum k times

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

3. Final Answer:

   Build a min heap and extract minimum k times -> Option B

4. Quick Check:

   Min heap extraction = kth smallest element [OK]

Hint: Extract min from min heap k times to get kth smallest [OK]

Common Mistakes:

• Using max heap instead of min heap
• Sorting array instead of using heap
• Confusing kth smallest with kth largest

2. Which of the following C++ STL functions is used to create a min heap from a vector?

easy

A. std::make_heap(v.begin(), v.end(), std::greater<int>())

B. std::push_heap(v.begin(), v.end())

C. std::make_heap(v.begin(), v.end())

D. std::pop_heap(v.begin(), v.end())

Solution

1. Step 1: Understand default heap behavior

   By default, std::make_heap creates a max heap.

2. Step 2: Use comparator for min heap

   Passing std::greater<int>() as comparator creates a min heap.

3. Final Answer:

   std::make_heap with std::greater comparator -> Option A

4. Quick Check:

   std::make_heap + std::greater = min heap [OK]

Hint: Use std::greater<int>() with make_heap for min heap [OK]

Common Mistakes:

• Using default make_heap creates max heap
• Confusing push_heap and make_heap
• Using pop_heap to create heap

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

std::vector<int> v = {7, 10, 4, 3, 20, 15};
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap(v.begin(), v.end());
int k = 3;
int kthSmallest;
for (int i = 0; i < k; i++) {
    kthSmallest = minHeap.top();
    minHeap.pop();
}
std::cout << kthSmallest << std::endl;

medium

A. 10

B. 4

C. 7

D. 3

Solution

1. Step 1: Build min heap from vector

   The min heap elements in order of extraction are 3, 4, 7, 10, 15, 20.

2. Step 2: Extract min 3 times

   Extracted elements: 3 (1st), 4 (2nd), 7 (3rd). So, kth smallest (k=3) is 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   3rd smallest element = 7 [OK]

Hint: Extract min k times from min heap to get kth smallest [OK]

Common Mistakes:

• Confusing kth smallest with kth largest
• Off-by-one error in loop
• Not popping from heap after top

4. Identify the error in the following code to find the kth smallest element using a min heap:

std::vector<int> nums = {5, 3, 8, 4, 2};
std::priority_queue<int> minHeap(nums.begin(), nums.end());
int k = 2;
int result;
for (int i = 0; i < k; i++) {
    result = minHeap.top();
    minHeap.pop();
}
std::cout << result << std::endl;

medium

A. priority_queue creates max heap by default, not min heap

B. Loop should run k+1 times

C. pop() should be called before top()

D. Vector initialization syntax is incorrect

Solution

1. Step 1: Check priority_queue default behavior

   By default, std::priority_queue is a max heap, so it will give the largest element first.

2. Step 2: Effect on kth smallest extraction

   Extracting top k times from max heap gives kth largest, not kth smallest.

3. Final Answer:

   priority_queue creates max heap by default, not min heap -> Option A

4. Quick Check:

   Default priority_queue = max heap [OK]

Hint: Use comparator for min heap; default is max heap [OK]

Common Mistakes:

• Assuming priority_queue is min heap by default
• Wrong loop count for kth element
• Calling pop before top

5. Given a large unsorted array with possible duplicate elements, which approach using a min heap is most efficient to find the kth smallest unique element?

hard

A. Build a min heap of all elements and extract unique elements until kth unique is found

B. Sort the array and iterate to find kth unique element

C. Use a max heap of size k to track kth smallest unique element while iterating

D. Use a hash set to remove duplicates, then build min heap and extract kth element

Solution

1. Step 1: Remove duplicates using hash set

   Using a hash set removes duplicates efficiently, reducing the data size.

2. Step 2: Build min heap from unique elements and extract kth

   Building min heap from unique elements and extracting kth smallest is efficient and correct.

3. Final Answer:

   Use a hash set to remove duplicates, then build min heap and extract kth element -> Option D

4. Quick Check:

   Remove duplicates first, then min heap extraction [OK]

Hint: Remove duplicates first, then use min heap for kth smallest [OK]

Common Mistakes:

• Extracting kth smallest without removing duplicates
• Using max heap instead of min heap
• Sorting entire array unnecessarily