Update a Bounded Heap

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement largest_k_sorted(values, k). Scan values once while keeping at most k candidates in a min-heap. Return the retained k largest values in ascending order. k may be zero or larger than len(values).

Starter code

def largest_k_sorted(values, k):
    pass

Test cases

retain-three

{
  "args": [
    [
      5,
      1,
      9,
      3,
      9,
      2
    ],
    3
  ]
}

Expected: [5,9,9]

zero-capacity

{
  "args": [
    [
      4,
      2
    ],
    0
  ]
}

Expected: []

Wizard outline

Step 1: Handle zero retained candidates
Return an empty result when k is zero. No heap operation is valid or necessary when the capacity is zero.
Step 2: Retain every value below capacity
Push all values when the input never fills k slots. Before the heap reaches capacity, every scanned value belongs among the retained candidates.
Step 3: Keep the first k candidates bounded
Never grow the heap past k entries. The memory invariant is at most k retained candidates throughout the scan.
Step 4: Replace the smallest retained candidate
Use heapreplace when a later value is larger than heap[0]. The minimum retained value is the only candidate that can leave when a better value arrives.

Footguns and prerequisites

Using a max-heap and evicting its root discards the best candidate instead of the weakest.
Pushing before handling k == 0 grows a heap that should remain empty.
arrays strings two pointers sliding window

Reviewed references

Python heapq — Heap Queue Algorithm

Prepared Interview Problems

Kth Largest Element in an Array(opens in a new tab)
Update a Bounded Heap isolates after each value, the heap contains the largest min(k, processed_count) values seen so far. That focused state discipline is required when implementing kth largest array as a complete Interview Problem.
Kth Smallest in a Sorted Matrix(opens in a new tab)
Update a Bounded Heap isolates after each value, the heap contains the largest min(k, processed_count) values seen so far. That focused state discipline is required when implementing kth smallest sorted matrix as a complete Interview Problem.
Seat Reservation Manager(opens in a new tab)
Update a Bounded Heap isolates after each value, the heap contains the largest min(k, processed_count) values seen so far. That focused state discipline is required when implementing seat reservation manager as a complete Interview Problem.
Sort Characters by Frequency(opens in a new tab)
Update a Bounded Heap isolates after each value, the heap contains the largest min(k, processed_count) values seen so far. That focused state discipline is required when implementing sort characters by frequency as a complete Interview Problem.
Top K Frequent Elements(opens in a new tab)
Update a Bounded Heap isolates after each value, the heap contains the largest min(k, processed_count) values seen so far. That focused state discipline is required when implementing top k frequent elements as a complete Interview Problem.

Recommended approach and implementation

Streaming top-k selection needs only the current k best candidates, with the weakest candidate exposed at the heap root. After each value, the heap contains the largest min(k, processed_count) values seen so far.

Why it works: Pushing fills the heap until k candidates exist; afterward, replacing its minimum only for a larger value preserves precisely the k largest processed values. Sorting the retained heap in ascending order produces exactly the requested result.

import heapq

def largest_k_sorted(values, k):
    heap = []
    for value in values:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif k and value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap)