K-th largest element

Find the k-th largest value without sorting everything, by keeping only the k biggest values seen so far.

Time O(n log k)Space O(k)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Keep a min-heap of size k. Whenever it grows to k + 1, throw out the smallest. What survives is the k largest values, and the smallest of those is the answer.

Code

C++PythonC#

int kthLargest(const vector<int>& a, int k) {
    priority_queue<int, vector<int>, greater<int>> heap; // min-heap
    for (int x : a) {
        heap.push(x);
        if ((int)heap.size() > k) heap.pop();
    }
    return heap.top();
}

import heapq

def kth_largest(a: list[int], k: int) -> int:
    heap = []  # min-heap
    for x in a:
        heapq.heappush(heap, x)
        if len(heap) > k: heapq.heappop(heap)
    return heap[0]

public static int KthLargest(int[] a, int k) {
    var heap = new PriorityQueue<int, int>(); // min-heap
    foreach (int x in a) {
        heap.Enqueue(x, x);
        if (heap.Count > k) heap.Dequeue();
    }
    return heap.Peek();
}

Tips

A min-heap for the largest values sounds backwards, but the minimum is the one you need to evict.
For the k smallest, use a max-heap by negating the priority.

In the .NET library

PriorityQueue<TElement, TPriority> dequeues the lowest priority first. Pass -x as the priority, or a custom IComparer, to get a max-heap.