Ordered data: heaps, sorted lists, queues and deques

Many coding problems ask for the "next" thing: the most urgent job, the oldest request, the cheapest offer. A list, a dictionary and a set (the last lesson) do not answer these questions fast. A wrong choice passes small tests, then is too slow for thousands of items.

A weak answer sorts the whole list every time it needs the smallest item. A strong answer names the question, such as "I always need the smallest". Then it picks the structure made for that question, and says what each call costs.

At SDE-1 level you should know that special structures exist for "smallest first" and for "both ends". At SDE-2 level you should combine them: handle ties, cancel an item, and hold back work that is not ready. Interviewers often ask: "How do you get the next job fast, and how do you cancel a job?"

A queue is a line where items leave in the order they came in: first in, first out. A ticket counter is a queue. In a hospital emergency room, the most urgent patient goes first, and among equal cases the one who waited longest goes first. That is a priority queue. A phone directory is sorted by name, so you can read all names between "Rao" and "Reddy".

This lesson adds questions about order:

• Which one is the smallest, or the most urgent?
• What is between a and b? What is just above this value?
• Which one has waited longest? We add at one end and take from the other end.
• Which one was used longest ago?

Each question has a structure made for it.

Heap: the smallest is always in front

A heap always keeps the smallest item at position 0 of its list. Adding an item (heappush) and removing the smallest (heappop) each cost about log n steps. Looking at the smallest without removing it (heap[0]) costs 1 step. Python's heapq library works on a normal list. The rest of the list is only roughly in order: a heap is not a sorted list.

Inside, a heap is a pile in levels, and each level holds twice as many items as the one above. So n items need only about log n levels, and a push or a pop moves an item along at most that many. You use heapq; you do not write this part.

To get "most urgent first, and among equals the first one submitted", store a tuple as the item: (priority, number, job_id). Python compares the first value, then the second if the first values are equal. Here 1 is the most urgent priority. The number is a counter that goes up with each submit. It breaks ties in favour of the earlier submit. It also keeps Python from comparing the job ids. If two tuples tie on the first two values, Python compares the third. A third value that cannot be compared raises a TypeError.

Lazy deletion: you cannot remove from the middle

A heap can only remove the smallest item. Removing from the middle of the list costs n steps and breaks the heap. The trick is lazy deletion: do not remove the item. Write its id in a set of cancelled ids. When the item reaches the front and is popped, check the set. If it is cancelled, drop it and pop again.

Sorted list and bisect: search and ranges

To ask "what is between 100 and 200?", keep a plain list in sorted order. The library bisect finds a place in log n steps. bisect_left(xs, v) is the first place where v can go. bisect_right(xs, v) is the first place after every v that is already there. insort inserts at the right place, but it costs n steps, because the items after it move one place. Python has no sorted dictionary. Keep a sorted list of the keys, plus a normal dictionary from key to value.

Deque: both ends in one step

A deque (say "deck"; short for double-ended queue) adds and removes at both ends in 1 step. append adds at the right end, and popleft removes at the left end. A list is slow at the front: pop(0) moves every other item, which is n steps. A deque suits a queue and a sliding window, such as "the events of the last 10 minutes". Add new events at the right end, and drop old events from the left end. With deque(maxlen=3), a full deque drops an item on one side when you add on the other.

Recency order: the idea behind LRU

A cache is a small store that keeps recent answers, so the next ask is fast. When it is full, something must go. Least recently used (LRU) means: throw out the item that was used longest ago. We need two things at once: find an item by its key, and move it to "most recent" when it is used. Both must take 1 step.

A dictionary alone finds by key. A linked list is a chain of items where each one points to the next and the previous. If you hold an item, you can move it to the end in 1 step. LRU joins the two: the dictionary finds the chain item, and the chain keeps the order of use. Python has this ready in OrderedDict. move_to_end(key) marks an item as used, and popitem(last=False) removes the oldest.

Two queues for delayed work

Some work must not start before a given time. A heap by priority may give it out too early. A heap by time loses the priority. So use two heaps. The delayed heap is ordered by ready time, and the ready heap by priority. When a job's time comes, move it from the first to the second. The time comes in as an argument, now (the lesson on testable code).

Price levels: a dictionary of queues plus a sorted list

Think of a board where people offer tickets for sale. This is the shape of an order book. A buyer takes the cheapest offer first, and at the same price the earliest offer. Keep a dictionary from price to a deque of offers, and a sorted list of the prices that have offers. The cheapest price is prices[0].

Which structure costs what

In Java

The ideas are the same. The names change.

Run with Python 3.11. Assumption: the scheduler has these rules, made up for teaching. A job has an id, a priority (1 is most urgent) and a time when it may start. next_job(now) returns the most urgent job that may start at now. At the same priority, the job submitted first goes first. A cancelled job never runs, and a job that has run cannot be cancelled. The delayed heap holds (ready_at, number, job_id), and the ready heap holds (priority, number, job_id).

import heapq

class JobScheduler:
    def __init__(self):
        self._delayed = []
        self._ready = []
        self._priority = {}
        self._cancelled = set()
        self._started = set()
        self._count = 0

    def submit(self, job_id, priority, ready_at):
        if job_id in self._priority:
            raise ValueError(f"job {job_id} already exists")
        self._priority[job_id] = priority
        heapq.heappush(self._delayed, (ready_at, self._count, job_id))
        self._count += 1

submit checks first and changes last, as in the lesson on bad input and errors. cancel refuses a job that is unknown, already cancelled or already started.

    def cancel(self, job_id):
        if job_id not in self._priority:
            return False
        if job_id in self._cancelled or job_id in self._started:
            return False
        self._cancelled.add(job_id)
        return True

The next method moves the jobs whose time has come, and then pops the ready heap.

    def next_job(self, now):
        while self._delayed and self._delayed[0][0] <= now:
            ready_at, number, job_id = heapq.heappop(self._delayed)
            priority = self._priority[job_id]
            heapq.heappush(self._ready, (priority, number, job_id))
        while self._ready:
            priority, number, job_id = heapq.heappop(self._ready)
            if job_id in self._cancelled:
                continue
            self._started.add(job_id)
            return job_id
        return None

Reading the code:

• while a and b: repeats the block as long as both are true. Here self._delayed and stops us from reading [0] of an empty list.
• self._delayed[0][0] is the ready time (first part) of the top item (first item).
• ready_at, number, job_id = t gives the three parts of a tuple three names.
• continue means "go to the next round of the loop". Here it is the lazy deletion.

Now submit five jobs. Job B has priority 1 but may start only at time 5.

s = JobScheduler()
s.submit("A", 2, 0)
s.submit("B", 1, 5)
s.submit("C", 1, 0)
s.submit("D", 1, 0)
s.submit("E", 3, 0)
print(s.cancel("D"), s.cancel("D"), s.cancel("Z"))

It prints True False False. Cancelling D works once. A second cancel of D, or a cancel of the unknown Z, returns False. Now take jobs at time 0. The list [s.next_job(0) for _ in range(4)] is a comprehension. Here range(4) counts 0, 1, 2, 3, and _ is a name for a value we do not use.

print([s.next_job(0) for _ in range(4)])
print(s.next_job(4), s.next_job(5), s.next_job(5))
print(s.cancel("C"))

At the start of the first call, the jobs A, C, D and E move to the ready heap. The picture shows this moment. B stays in the delayed heap.

The two heaps of the job scheduler at time 0, after the jobs A, C, D and E have moved and before the first pop. The delayed heap, ordered by ready time, holds job B, which is ready at time 5. The ready heap holds C, A, D and E, and they pop in the order C, D, A, E. D is cancelled. An arrow from the delayed heap to the ready heap is labelled time is up.

The output is ['C', 'A', 'E', None], then None B None, then False. The pops go like this:

1. C comes out (priority 1, number 2).
2. D is popped (priority 1, number 3) and dropped, because it is cancelled. Then A comes out (priority 2).
3. E comes out (priority 3).
4. The fourth call finds nothing ready, because B waits until time 5.

At time 4 B is still delayed. At time 5 B moves and runs. The last line is False, because C has already run.

The predict box. Without the cancel, the order is C, D, A, E: priority first, then the submit number. The counter breaks the tie between C and D.

The cost. Assumption: 10,000 jobs wait. Halving 10,000 until you reach 1 takes about 13.3 halvings (rounded). Sorting the jobs on every call costs about 10,000 x 13.3 = 133,000 steps. A heap has about 14 levels (13.3 rounded up), so a pop costs about 14 steps.

A sorted list. Insert prices and ask for the range from 110 to 200:

import bisect

prices = []
for price in [150, 100, 120, 100, 300]:
    bisect.insort(prices, price)
lo = bisect.bisect_left(prices, 110)
hi = bisect.bisect_right(prices, 200)
print(prices, lo, hi, prices[lo:hi])

It prints [100, 100, 120, 150, 300] 2 4 [120, 150]. The first place for 110 is position 2, and the first place after every 200 is position 4. The slice prices[lo:hi] is the list from position lo up to, but not including, position hi.

A sliding window. Count the events of the last 10 minutes. Assumption: the window is at least 1, and an event at exactly now - 10 is outside it.

from collections import deque

class RecentCount:
    def __init__(self, window):
        self._window = window
        self._times = deque()

    def add(self, now):
        self._times.append(now)
        while self._times and self._times[0] <= now - self._window:
            self._times.popleft()
        return len(self._times)

counter = RecentCount(10)
print([counter.add(t) for t in [1, 4, 8, 11, 12, 30]])

It prints [1, 2, 3, 3, 4, 1]. At time 11 the event at time 1 is dropped. At time 30 all earlier events are dropped.

An LRU order with room for 3 items:

from collections import OrderedDict

class LruOrder:
    def __init__(self, capacity):
        self._capacity = capacity
        self._items = OrderedDict()

    def get(self, key):
        if key not in self._items:
            return None
        self._items.move_to_end(key)
        return self._items[key]

    def put(self, key, value):
        self._items[key] = value
        self._items.move_to_end(key)
        if len(self._items) > self._capacity:
            self._items.popitem(last=False)

    def keys(self):
        return list(self._items)

Put a, b and c, call get("a"), and print keys(). It gives ['b', 'c', 'a'], oldest first. Then put d: there are four items, so b goes. keys() gives ['c', 'a', 'd'], and get("b") gives None.

The offer board. The dictionary holds a deque of offers for each price. The sorted list holds the prices that have offers.

class OfferBoard:
    def __init__(self):
        self._levels = {}
        self._prices = []

    def add(self, offer_id, price):
        if price not in self._levels:
            self._levels[price] = deque()
            bisect.insort(self._prices, price)
        self._levels[price].append(offer_id)

The method that takes the cheapest offer removes a price from both places when it has no offers left. (del d[k] removes the key k from a dictionary.)

    def take_cheapest(self):
        if not self._prices:
            return None
        price = self._prices[0]
        offer_id = self._levels[price].popleft()
        if not self._levels[price]:
            del self._levels[price]
            self._prices.pop(0)
        return offer_id, price

Add the offers t1 at 500, t2 at 400, t3 at 400 and t4 at 450. The dictionary holds 400: [t2, t3], 450: [t4] and 500: [t1], and the sorted prices are [400, 450, 500]. Five calls of take_cheapest give ('t2', 400), ('t3', 400), ('t4', 450), ('t1', 500) and then None.

A heap solves the "next smallest" question. Each add and each take costs about log n steps, not n x log n for a sort on every call. It costs the order: only the front is known, and you cannot remove from the middle without lazy deletion. A sorted list solves ranges and costs n steps for every insert. A deque solves a fast queue and a window. I would change from a heap to a sorted list when the question asks for ranges or for all items in order.

"A heap keeps all the items sorted." Only the smallest is guaranteed to be at the front. Pushing 5, 3, 8, 1, 9 and 2 gives the list [1, 3, 2, 5, 9, 8]. Popping them one by one gives 1, 2, 3, 5, 8, 9.

"To cancel a job, remove it from the heap." That costs n steps and breaks the heap. Mark it as cancelled and skip it when it reaches the front.

"pop(0) on a list is fine for a queue." It moves every other item, so it costs up to n steps. For 100,000 items, 100,000 pops can cost up to 100,000 x 100,000 = 10,000,000,000 steps. A deque takes 1 step.

1. Which structure answers each question? (a) The next most urgent job. (b) All prices between 100 and 200. (c) The requests of the last 10 minutes. (d) The key that was used longest ago.
2. A scheduler has 20,000 waiting jobs. Halving 20,000 until you reach 1 takes about 14.3 halvings. About how many steps does it cost to sort them on every call? About how many does a heap pop cost, rounded up?
3. A teammate cancels a job by calling heap.remove(entry) on the list. What is wrong, and what do you do instead?