Kth Largest Element

Find the kth largest element using a max heap with O(n + k log n) time complexity

Max Heap (Tree View)

Heap Array

Extracted Elements (Largest to Smallest)

Phase

Current operation

Heap Size

Elements in heap

k

Target position

Result

kth largest

Click "Step" or "Play" to build the heap and find the kth largest element

Root (Max)

Current

Parent

Child

Extracted

Python Code - Kth Largest Element

                def findKthLargest(nums, k):
            
                    heap = []
            
                    for n in nums:
            
                        heappush(heap, n) # sift-up
            
                    extracted = []
            
                    while len(extracted) < k:
            
                        extracted.append(heappop(heap))
            
                    return extracted[k - 1]
            
                # sift-up: bubble up if > parent
            
                # sift-down: sink to larger child
            
                # Max heap: parent >= children

Complexity Analysis

Time Complexity O(n + k log n) Space Complexity O(n)

Time Complexity: O(n + k log n)

Breakdown

Build max-heap (heapify): O(n) via Floyd's algorithm
Extract max k times: k × O(log n) sift-down
Total: O(n) + O(k log n) = O(n + k log n)
When k = 1: O(n), when k = n: O(n log n)

T(n,k) = O(n) + k × O(log n) = O(n + k log n)

Mathematical Intuition

Floyd's heapify is O(n), not O(n log n), because most nodes are near leaves with small subtrees. The sum Σ h(i) over all nodes (where h(i) is height) equals n - ⌊log n⌋ - 1, not n log n. Each extraction removes the root and restores heap property in O(log n).

Key Insight

For k << n, heap selection beats sorting. QuickSelect offers O(n) expected time but O(n²) worst-case without median-of-medians.

Space Complexity: O(n)

Breakdown

Heap array: stores all n elements
In-place heapify possible: O(1) extra
If input must be preserved: O(n) copy
Sift operations: O(1) temporary variables

S(n) = O(n) for heap storage (or O(1) if in-place)

Mathematical Intuition

A binary heap is stored as a complete binary tree in an array: parent at index i has children at 2i+1 and 2i+2. This implicit structure requires no pointer overhead. If modifying the input is allowed, heapify is in-place with O(1) auxiliary space.

Key Insight

Alternative: use a min-heap of size k to find kth largest in O(n log k) time and O(k) space—better when k << n.