Find the Kth Largest Element Using a Min-Heap

• Min-heap of size k – Java's PriorityQueue is a min-heap by default, with peek returning the smallest.
• Offer and poll – for each element, offer it; if size exceeds k, poll the smallest out.
• Root is answer – after processing all elements, peek() returns the kth largest.
• O(n log k) time – each offer and poll on a size-k heap is O(log k), done n times.
• O(k) space – only k elements are held at any time, enabling stream processing.

What is the problem?

Given an array of numbers and a value k, find the kth largest element. In a banking context, the reporting dashboard at National Bank of India needs to surface the top few largest transactions from a high-volume stream.

Why not just sort?

Sorting costs O(n log n) and requires the entire array in memory. The min-heap approach costs O(n log k), which is faster when k is much smaller than n, and it works on streams because only k elements are held at any time.

How does the min-heap approach work?

Create a PriorityQueue (min-heap). For each element in the array, offer it to the heap. If the heap grows beyond k, poll the smallest. After all elements are processed, the heap's root is the kth largest.

package com.bank.service;

import java.math.BigDecimal;
import java.util.PriorityQueue;

public class TopKFinder {

    public static BigDecimal findKthLargest(BigDecimal[] amounts, int k) {
        if (amounts == null || amounts.length < k || k <= 0) {
            throw new IllegalArgumentException("Invalid input");
        }
        PriorityQueue<BigDecimal> minHeap = new PriorityQueue<>(k);
        for (BigDecimal amount : amounts) {
            minHeap.offer(amount);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        BigDecimal[] dailyTxns = {
            new BigDecimal("15000.00"),
            new BigDecimal("42500.75"),
            new BigDecimal("8000.00"),
            new BigDecimal("67200.50"),
            new BigDecimal("3100.25"),
            new BigDecimal("91000.00"),
            new BigDecimal("28400.00")
        };
        int k = 3;
        BigDecimal result = findKthLargest(dailyTxns, k);
        System.out.println("The " + k + "rd largest transaction: Rs." + result);
    }
}

The 3rd largest transaction: Rs.42500.75

Why does a min-heap work and not a max-heap?

A min-heap keeps the smallest element at the root. By maintaining only k elements, the root is the smallest of the k largest, which is exactly the kth largest. A max-heap would keep the largest at the root, which is the 1st largest, and finding the kth would require popping k times, which is less efficient for streams.

What is the time and space complexity?

• Time: O(n log k) because each offer and poll on a heap of size k is O(log k), and you do this n times.
• Space: O(k) because only k elements are stored at any time.
• When k is close to n, this degrades to O(n log n), matching sorting.

What is the Quickselect alternative?

Quickselect partitions the array like quicksort but recurses into only one side. It finds the kth largest in expected O(n) time, but its worst case is O(n^2). It also requires the entire array in memory and cannot stream.

| Aspect | Min-Heap | Quickselect |
|---|---|---|
| Time (average) | O(n log k) | O(n) |
| Time (worst) | O(n log k) | O(n^2) |
| Space | O(k) | O(1) in-place |
| Streaming | Yes | No |
| Deterministic | Yes | No (randomised) |

What are common mistakes?

The most common mistake is using a max-heap instead of a min-heap. Another is forgetting to check that k is valid (between 1 and n inclusive).

// Wrong: max-heap keeps the largest, not the kth largest
PriorityQueue<BigDecimal> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
// After n elements, peek() gives the 1st largest, not the kth

// Correct: min-heap of size k
PriorityQueue<BigDecimal> minHeap = new PriorityQueue<>(k);

How does this extend to top-k elements?

After the main loop, the heap contains exactly the k largest elements. You can drain the heap to get all of them, though they come out in min-to-max order. If you need them in descending order, drain into a list and reverse.

What should a senior engineer know?

A senior engineer chooses the min-heap for stream processing and bounded memory, and Quickselect for in-memory data when expected-linear time matters. The senior also knows about the median-of-medians variant that guarantees worst-case O(n) for Quickselect, though its constant factor is too high for practical use. For the banking dashboard, the stream-friendly min-heap is the right choice because transaction feeds are unbounded.