Finding the Kth Smallest Element in an Array Using Heap (Min Heap) in Python

Problem Explanation

Given an integer array arr[] and an integer k, the task is to find the kth smallest element in the array.

The kth smallest element is determined based on the sorted order of the array.

Example:

• Input: arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10], k = 4
  Output: 5

• Input: arr = [7, 10, 4, 3, 20, 15], k = 3
  Output: 7

---

Method Used: Min Heap

A Min Heap is a data structure where the smallest element is always at the root.

Steps:

1. Convert the array into a min heap
2. Remove the smallest element k-1 times
3. The next removed element will be the kth smallest

---

Why This Method?

• More efficient than repeated minimum search
• Time complexity: O(n + k log n)
• Does not require full sorting
• Useful for large datasets

---

Python Code

import heapq

class Solution:
    def kthSmallest(self, arr, k):
        heapq.heapify(arr)          # Convert list into a min heap

        for i in range(k - 1):      # Remove smallest k-1 elements
            heapq.heappop(arr)

        return heapq.heappop(arr)   # Return kth smallest element

---

Code Explanation (Line by Line)

• import heapq
  Imports Python’s built-in heap library.

• class Solution:
  Defines the class as required by the platform.

• def kthSmallest(self, arr, k):
  Function to find the kth smallest element.

• heapq.heapify(arr)
  Converts the list into a min heap in-place, where the smallest element is at the root.

• for i in range(k - 1):
  Loop runs k-1 times to remove the smallest elements.

• heapq.heappop(arr)
  Removes the smallest element from the heap.

• return heapq.heappop(arr)
  After removing k-1 elements, the next smallest element is the kth smallest.

---

Output

Input:

arr = [10, 5, 4, 3, 48, 6, 2, 33, 53, 10]
k = 4

Output:

5

---

Key Takeaway

Using a Min Heap allows us to efficiently extract the smallest elements without sorting the entire array, making it a better approach for larger inputs.

---