PART 4 · DSA AND COMPLEXITY · CHAPTER 28

Heaps and greedy choices

FreeLesson 53 of 78

A heap always hands you the smallest item in O(log n). A greedy algorithm makes the locally best choice at each step. Together they solve most scheduling questions.

MINIMUM ROOMS, AND MOST NON-OVERLAPPING JOBSPYTHON 3.12

import heapq

bookings = [("05-01", "05-04"), ("05-03", "05-06"), ("05-06", "05-08"),
            ("05-02", "05-05"), ("05-04", "05-07")]

def rooms_needed(stays):
    ends = []                                    # min-heap of check-outs
    for start, end in sorted(stays):
        if ends and ends[0] <= start:            # a room is free again
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)            # open another room
    return len(ends)

def max_jobs(windows):              # greedy: earliest finish
    count, last_end = 0, ""
    for start, end in sorted(windows, key=lambda w: w[1]):
        if start >= last_end:
            count, last_end = count + 1, end
    return count

print(rooms_needed(bookings), max_jobs(bookings))

Output

3 2

RUNNING MEDIAN OF A STREAM WITH TWO HEAPSPYTHON 3.12

import heapq

class RunningMedian:                      # two heaps
    def __init__(self):
        self.low, self.high = [], []      # max-heap (negated), min-heap
    def add(self, x):
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))
    def median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

rm = RunningMedian()
for latency in [120, 340, 95, 410, 180, 150]:
    rm.add(latency)
    print(latency, "->", rm.median())

Output

120 -> 120
340 -> 230.0
95 -> 120
410 -> 230.0
180 -> 180
150 -> 165.0

Heap recipe	Keep in the heap	Cost
Top k largest	The k largest so far, smallest on top	O(n log k)
k-th largest	Same; the answer is the top	O(n log k)
Merge k sorted files	One head item per file	O(n log k)
Rooms / machines needed	End times of busy rooms	O(n log n)
Running median	Lower half (max-heap) and upper half (min-heap)	O(log n) per item
Next job to run by priority	(priority, job) pairs	O(log n) per push or pop

Practice before you move on

Use heapq.nsmallest to find the three cheapest products in products.csv.
Feed the running median the amounts of orders.csv one by one and print the final median.