Keeping only k candidates

The counterintuitive one: to track the k largest, keep a heap of the smallest of them.

Key idea

The inversion

To keep track of the k largest values seen so far, use a min-heap holding exactly those k values. The smallest of the k sits at the top, which is precisely the one that gets displaced when something better arrives.

That inversion is the thing to internalize. The heap's cheap operation should be the one you need most often, and here the frequent question is which of my keepers is the weakest.

1import heapq2 3def k_largest_streaming(values, k):4    heap = []                       # holds at most k, smallest on top5    for value in values:6        heapq.heappush(heap, value)7        if len(heap) > k:8            heapq.heappop(heap)     # drop the weakest keeper9    return sorted(heap, reverse=True)10 11print(k_largest_streaming([5, 1, 8, 3, 9, 2], 3))

Quick check· 5 min

Which heap for which question?

You must maintain the k smallest values from an ongoing stream. What kind of heap should hold them, and what sits at its top?

A max-heap of the k smallest, with the largest of them on topA min-heap of the k smallest, with the smallest of them on topA max-heap of everything seen so farA min-heap of everything seen so far

Problem· 18 min

Kth Largest Element In A Stream

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 16 min

Last Stone Weight

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Heaps and Priority Queues

82 / 170

Heaps and Priority QueuesLesson 2 of 8About 51 min

Keeping only k candidates

The counterintuitive one: to track the k largest, keep a heap of the smallest of them.

Key idea

The inversion

That inversion is the thing to internalize. The heap's cheap operation should be the one you need most often, and here the frequent question is which of my keepers is the weakest.

1import heapq2 3def k_largest_streaming(values, k):4    heap = []                       # holds at most k, smallest on top5    for value in values:6        heapq.heappush(heap, value)7        if len(heap) > k:8            heapq.heappop(heap)     # drop the weakest keeper9    return sorted(heap, reverse=True)10 11print(k_largest_streaming([5, 1, 8, 3, 9, 2], 3))

Quick check· 5 min

Which heap for which question?

You must maintain the k smallest values from an ongoing stream. What kind of heap should hold them, and what sits at its top?

A max-heap of the k smallest, with the largest of them on topA min-heap of the k smallest, with the smallest of them on topA max-heap of everything seen so farA min-heap of everything seen so far

Problem· 18 min

Kth Largest Element In A Stream

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 16 min

Last Stone Weight

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.