Extract smallest elements
Use a min-heap to repeatedly extract the smallest available item in logarithmic time. About 8 minutes.
The Min-Heap property
In a min-heap, the smallest value is always at the top. When you remove it, the heap quietly reorganises itself in about log n steps so the next smallest value rises to the top.
It is like a tournament ladder: when the champion leaves, a few matches decide the new one, without replaying the whole tournament.
import heapq
heapq.heapify(nums)
res = []
for _ in range(k):
res.append(heapq.heappop(nums))
return resThe array drawn as a tree: index 0 on top, then 1 and 2, then 3, 4, 5. No pointers, just positions. It isn't a heap yet.
Heaps across languages
Every language ships a ready-made heap, so you rarely write one yourself. In Python, the heapq module turns a list into a min-heap and pops from it. In C++, the priority queue with a "greater" comparison is a min-heap. In Java, a PriorityQueue is a min-heap by default.
Learn the one in your language and you'll reuse it on many problems.
How long does it take to inspect (peek at) the smallest value in a min-heap of 1,000,000 items?
- AO(1) instant time
- BO(log n) time
- CO(n) time
Show the answer
O(1) instant time. The minimum is always right at the root (index 0), so reading it takes 1 step.
Extract smallest elements
Given an array of integers nums and an integer k (where 0 ≤ k ≤ nums.length), use a min-heap to extract the k smallest elements from the array in non-decreasing order.
nums = [7, 10, 4, 3, 20, 15], k = 3 → [3, 4, 7]
0 ≤ nums.length ≤ 100,000 · 0 ≤ k ≤ nums.length · -1,000,000 ≤ nums[i] ≤ 1,000,000