Kth Largest Element in an Array Using Heap (Python) – Two Efficient Approaches

Problem Overview

The task is to find the kth largest element in an unsorted array. Although sorting the array would work, it requires O(n log n) time, which is inefficient for this problem.

Heap-based solutions allow us to optimize this process by partially ordering elements instead of fully sorting the array.

---

Approach 1: Min-Heap of Size k

This approach maintains a min-heap that stores only the k largest elements seen so far.

Key Idea

• Use a min-heap
• Keep heap size limited to k
• The smallest element in the heap is the kth largest overall

Algorithm Steps

1. Initialize an empty min-heap
2. Traverse the array
3. If heap size is less than k, push the element
4. Otherwise, push the new element and remove the smallest one
5. After traversal, the heap root is the answer

Python Code

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []

        for num in nums:
            if len(min_heap) < k:
                heapq.heappush(min_heap, num)
            else:
                heapq.heappushpop(min_heap, num)

        return min_heap[0]

Complexity

• Time: O(n log k)
• Space: O(k)

---

Approach 2: Max-Heap Using Negatives

Since Python only provides a min-heap, we can simulate a max-heap by converting all values to their negatives.

Key Idea

• Negate all array elements
• Heapify the array
• Pop elements k-1 times
• The next popped element (after negation) is the kth largest

Algorithm Steps

1. Convert all elements to negative
2. Apply heapify
3. Pop from heap k-1 times
4. Pop once more and negate to get the answer

Python Code

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        for i in range(len(nums)):
            nums[i] = -nums[i]

        heapq.heapify(nums)

        for _ in range(k - 1):
            heapq.heappop(nums)

        return -heapq.heappop(nums)

Complexity

• Time: O(n + k log n)
• Space: O(1) extra

Note that this approach modifies the input array, which may not be ideal in all cases.

---

Comparison of Both Approaches

Aspect	Min-Heap (Size k)	Negatives + Heapify
Heap Size	k	n
Time Complexity	O(n log k)	O(n + k log n)
Space Complexity	O(k)	O(1) extra
Input Modified	No	Yes
Best For	Large arrays, small k	Quick implementation

---

Reference Implementations

Complete Python implementations for these heap-based solutions can be found at the following GitHub links:

• Kth Largest Element – Heap Solution (Link 1)
• Kth Largest Element – Heap Solution (Link 2)

Both approaches highlight how heaps can efficiently solve selection problems without sorting the entire dataset.