The kth biggest value
Find the kth largest value of an array by keeping a small min-heap that holds only the k biggest values seen so far. About 14 minutes.
Keep only the k biggest
Sorting everything to find the kth largest does more work than needed. You only care about the k biggest values, and among them, the smallest one. That one is the answer.
Keep a collection of at most k values. When a new value arrives, add it. If the collection now has more than k values, throw out the smallest, because it cannot be among the k biggest.
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)Add 3 and 2. The heap holds 2 and 3, with 2 on top.
The collection is a min-heap
Both operations need the smallest value in the collection. A min-heap keeps its smallest value on top, adds a value in about log k steps, and removes the smallest in about log k steps.
After all values have been processed, the heap holds exactly the k biggest, and its top, the smallest of them, is the kth largest. Python's heap module is a min-heap on a list. Java uses a priority queue, and C++ a priority queue with a greater-than ordering.
return heap[0]
Why does the top of the size-k min-heap equal the kth largest?
- AThe heap holds the k biggest values, and the top is the smallest of those
- BThe top is the biggest value
- CThe top is the middle value
Show the answer
The heap holds the k biggest values, and the top is the smallest of those. The kth largest is the smallest of the k largest.
Kth largest element in an array
Given an integer array nums and an integer k, return the kth largest element of the array, counted in sorted order (so duplicates count separately). It is guaranteed that 1 ≤ k ≤ the length of nums.
nums = [3, 2, 1, 5, 6, 4], k = 2 → 5
1 ≤ k ≤ length of nums ≤ 100,000 · -10,000 ≤ nums[i] ≤ 10,000