Keep the Three Loudest Readings of a Day Without Sorting the Day

Sorting every reading orders thousands of values that will never be in the answer; a heap of three keeps only the candidates.

A min-heap of three finds the three largest readings in one pass and holds three values, where sorting holds and orders every reading. A noise meter beside a building site logs a reading in decibels every minute, and the site manager wants the three loudest of the day. Ten readings show the method: 62 71 55 80 67 90 58 74 69 85. A real day has 1,440, and the meter sends them one at a time.

The brute force sorts every reading, loudest first, and takes the first three. That costs O(n log n) time and O(n) space for n readings, and it cannot start until the day's last reading is in. The wasted work is the order it puts on readings that will never be in the answer: of 1,440, it carefully ranks the 1,437 that are thrown away. A max-heap of every reading, popped three times, is a half-step that still holds all n values. The answer needs only the three loudest so far, and the quietest of those is the one each new reading has to beat.

Sorting the day against a heap of three

Sort, then sliceO(n log n) time, O(n) space

Wait for every reading, sort them all loudest first, and take the first three.

Heap of threeO(n log 3) time, O(1) space

Keep the three loudest so far in a min-heap. Each new reading is compared with the quietest of them, on top, and replaces it only if louder.

The heap of three as the readings arrive

Inputreadings 62 71 55 80 67 90 58 74 69 85; cells are the heap's array, top first

62 dB: pushed
1. 62
The heap has room: 62 goes in
71 dB: pushed
1. 62
2. 71
71 goes in
55 dB: pushed
1. 55
2. 71
3. 62
55 goes in and rises to the top as the quietest; the heap is full
80 dB: replaced 55
1. 62
2. 71
3. 80
80 beats 55, which can no longer be among the three loudest
67 dB: replaced 62
1. 67
2. 71
3. 80
67 beats 62
90 dB: replaced 67
1. 71
2. 90
3. 80
90 beats 67, and 71 becomes the quietest of the three
58 dB: skipped
1. 71
2. 90
3. 80
58 is quieter than 71, so it is skipped
74 dB: replaced 71
1. 74
2. 90
3. 80
74 beats 71
69 dB: skipped
1. 74
2. 90
3. 80
69 is quieter than 74, so it is skipped
85 dB: replaced 74
1. 80
2. 90
3. 85
85 beats 74, leaving 80 on top

ResultThe three loudest readings are 90, 85 and 80 dB.

The listing runs both versions on the ten readings and reports how many values each had to hold.

loudest.pypy

import heapq

readings = [62, 71, 55, 80, 67, 90, 58, 74, 69, 85]


def sort_then_slice(values: list[int], k: int) -> list[int]:
    return sorted(values, reverse=True)[:k]


def heap_of_k(values: list[int], k: int) -> list[int]:
    heap: list[int] = []
    for value in values:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap, reverse=True)


print("sorted, then sliced:", sort_then_slice(readings, 3), "holding", len(readings), "values")
print("heap of three:      ", heap_of_k(readings, 3), "holding 3 values")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

sorted, then sliced: [90, 85, 80] holding 10 values
heap of three:       [90, 85, 80] holding 3 values

Both give 90, 85 and 80. With k fixed at 3, log k is a constant, so the heap's pass is O(n) time and O(1) extra space, against O(n log n) and O(n) for sorting, and it has its answer ready at any minute of the day rather than only at the end. For k close to n the gap closes, since O(n log k) approaches O(n log n), and sorting is the simpler choice.

Heaps

← → move through sections and cards