Data Structures

A tea shop takes orders on slips of paper. The owner could keep them in a box, in a pile, or in a line on a nail. If tea must go out in the order it was asked for, a line on the nail is best: the oldest slip is always at one end. If she often needs one customer’s slip, a box with a section for each table is better. The slips are the same; only the way they are kept changes what is easy.

A data structure is a way of keeping data in a program so that the operations the program needs are simple and fast. You know two already. A list keeps values in order and finds one by its position at once, marks[500]; a dictionary finds a value by its key at once, menu["tea"]. But finding a value in a list (is 47 anywhere?) means looking at the items one by one, and a dictionary has no order of its own that you can sort or take “the smallest” from.

This unit describes each structure in two ways:

• What it does: the operations it offers and the rules they follow, such as “take back the item put in last”. A structure described only by its operations is called an abstract data type. It is Unit 1’s idea of an interface: what you can ask, not how it is done.
• How it does it: the data inside and the code of each operation. This is the implementation. One abstract data type can have several implementations, each fast at different things.

For each operation you will ask the question from Grade 9: how does its work grow as the data grows? A constant operation, O(1), takes the same few steps for ten items or ten million. A linear one, O(n), looks at every item, so twice the items means twice the work. A logarithmic one, O(log n), halves what is left at each step, so twice the items means just one step more.

Look at the plates at a wedding feast, piled at the end of the table. The cook puts each washed plate on the top, and each guest takes one from the top. Nobody pulls one from the middle or the bottom. The plate put on last is the first one taken.

A stack is a pile like that, in a program. It has a top, and only the top can be reached. Its operations are:

• push: put an item on the top;
• pop: take the top item off, and give it back;
• peek: look at the top item without taking it;
• is empty: are there any items at all?

The rule is last in, first out, written LIFO: whatever was pushed last is popped first.

Here is a stack as a class, built on a Python list. The top is the list’s end, because append() and pop() at the end of a list are both quick: no other item moves.

class Stack:    """Last in, first out: items go on and come off at the top."""     def __init__(self):        self._items = []           # the top is the end of the list     def push(self, item):        self._items.append(item)     def pop(self):        if self.is_empty():            raise IndexError("pop from an empty stack")        return self._items.pop()     def peek(self):        if self.is_empty():            raise IndexError("peek at an empty stack")        return self._items[-1]     def is_empty(self):        return len(self._items) == 0     def __len__(self):        return len(self._items)  copies = Stack()for name in ["Asha", "Bimal", "Chhiring"]:    copies.push(name)              # each hands in an exam copy, on the pileprint("On top:", copies.peek())print("Marked first:", copies.pop())print("Marked next:", copies.pop())print("Still on the pile:", len(copies))

On top: ChhiringMarked first: ChhiringMarked next: BimalStill on the pile: 1

Chhiring handed in her copy last, so it was on top and marked first. __len__ is another of Python’s special methods, like Unit 1’s __str__: it is what len(copies) calls.

A Python list can already do all of this, with append() and pop(). So why write a class? Because a list can also do things a stack mustn’t: take an item from the middle, or sort the pile. The class offers only the stack’s operations, so a program that uses it can’t break the rule by mistake, and anyone reading copies.push(…) knows at once how the data is being used. That is Unit 1’s encapsulation again.

Undo

An editor that can undo keeps a stack of what came before. Each change pushes the text as it was; undo pops it back. A second stack makes redo possible: undo pushes the text it is leaving onto the redo stack, and redo pops it back.

class Editor:    """A one-line editor that can undo and redo."""     def __init__(self):        self.text = ""        self._undo = []            # a stack of earlier texts        self._redo = []            # a stack of texts that were undone     def _change(self, new_text):        self._undo.append(self.text)        self._redo.clear()         # a new change ends any chance to redo        self.text = new_text     def type(self, words):        self._change(self.text + words)     def delete(self, n):        self._change(self.text[:-n])     def undo(self):        if self._undo:            self._redo.append(self.text)            self.text = self._undo.pop()     def redo(self):        if self._redo:            self._undo.append(self.text)            self.text = self._redo.pop()  ed = Editor()ed.type("Dear Sir, I am sick")ed.delete(4)ed.type("unwell")print(ed.text)ed.undo()ed.undo()print(ed.text)ed.redo()print(ed.text)ed.type("ill")ed.redo()print(ed.text)

Dear Sir, I am unwellDear Sir, I am sickDear Sir, I am Dear Sir, I am ill

Follow the two stacks. Two undos take back “unwell” and then the deletion, so “sick” is back. A redo does the deletion again. Then a new change, typing “ill”, empties the redo stack, so the last redo() does nothing: you can’t redo something after you have changed the text another way.

This editor keeps a whole copy of the text for every change, which is fine for one line. A real editor, with a long document, pushes only a note of each change (“deleted these 4 letters at position 15”) and undoes it by doing the opposite. The stack is the same.

The back button

A web browser’s back and forward buttons work the same way, as two stacks. When you open a new page, the page you were on is pushed onto the back stack, and the forward stack is emptied. Back pushes the page you are on onto the forward stack and pops the back stack. Forward does the opposite.

Brackets that match

Here is a job a stack does perfectly. In (2 + 3) * [4 − (1 + 1)], every bracket that opens is closed, by the same kind of bracket, and the last one opened is always the first one closed. Python itself checks this in your programs before running them. The method: go along the text; push each opening bracket; at each closing bracket, pop the stack and check that it is the matching opener. At the end, the stack must be empty.

PAIRS = {")": "(", "]": "[", "}": "{"} def balanced(text):    """True if every bracket in the text is closed, in the right order."""    stack = []    for ch in text:        if ch in "([{":            stack.append(ch)        elif ch in PAIRS:            if not stack or stack.pop() != PAIRS[ch]:                return False       # nothing open, or the wrong kind    return len(stack) == 0         # anything still open is unclosed  for s in ["(2 + 3) * [4 - (1 + 1)]", "print((5 + 2)", "{[}]", "area = (l * b))"]:    print(balanced(s), " ", s)

True   (2 + 3) * [4 - (1 + 1)]False   print((5 + 2)False   {[}]False   area = (l * b))

The second has a bracket left open, the third closes [ with }, and the fourth closes a bracket that was never opened. Each mistake is found in a single pass along the text, with one push or pop per bracket: linear work.

The stack you have used all along

You have met one stack already. In Unit 2 the calls of a recursive function waited on the call stack: each call pushed on top, and the last call made was the first to finish. Unit 2 also turned a recursive flood fill into a loop with a list used as a stack, and Grade 10’s depth-first search was breadth-first search with a stack in place of its queue. Unit 4 shows where the processor keeps the call stack in memory.

At a bank in Nepal you press a button on a machine, and it prints a token with a number. You sit and wait. When a counter is free, a voice calls the next number, and the board shows it. The machine gives out numbers in order and the counters call them in the same order, so whoever came first is served first, and nobody can push in.

A queue keeps items in the order they arrived. Items join at the back and leave from the front. Its operations are:

• enqueue: add an item at the back;
• dequeue: take the item at the front off, and give it back;
• front (or peek): look at the front item without taking it;
• is empty.

The rule is first in, first out, written FIFO.

Figure 3.3 puts the two rules side by side.

Queues are everywhere a computer must be fair, or must not lose its place:

• The school’s one printer gets documents from twenty computers at once. They wait in a print queue and are printed in the order they were sent.
• When you type faster than a slow phone can show the letters, the key presses wait in a queue, so they appear in the order you typed them.
• A router whose line is busy keeps packets in a queue (Unit 6), and Grade 10’s breadth-first search kept the places still to visit in a queue, which is what made it search in rings.

Why not just a list?

In Grade 10 the queue was a Python list: append() at the back, pop(0) from the front. That works, and Grade 10 warned that pop(0) gets slow. Here is why. A list keeps its items in a row of numbered places, item 0 first. Take item 0 away, and every other item must move one place forward, so that the new front is item 0 again. For a queue of 10,000 tokens, serving one person moves 9,999 others. Taking from the front of a list is linear, O(n), and serving everybody is quadratic.

Python’s collections library has a structure made for queues, the deque (say “deck”, short for double-ended queue). Its append() adds at the back and its popleft() takes from the front, and neither moves the other items. Time the two:

import timefrom collections import deque for n in [10000, 20000, 40000]:    tokens = list(range(n))    start = time.perf_counter()    while tokens:        tokens.pop(0)                  # serve the front of a list    list_time = time.perf_counter() - start     tokens = deque(range(n))    start = time.perf_counter()    while tokens:        tokens.popleft()               # serve the front of a deque    deque_time = time.perf_counter() - start     print(f"{n:>6} tokens: list {list_time * 1000:7.1f} ms, deque {deque_time * 1000:5.1f} ms")

Press Run. Your times will differ from run to run and from computer to computer, but the pattern won’t: each time the number of tokens doubles, the list takes about four times as long (quadratic, because each of n pops moves up to n items), while the deque takes about twice as long (linear: one quick step per token). With a million tokens the difference would be minutes against a fraction of a second. How the deque manages it comes in the next section.

One fill, a stack or a queue

Unit 2’s flood fill kept its squares in a list taken from the end, a stack. Grade 10 filled a picture with breadth-first search, a queue Grade 10: Painting a picture, ring by ring. Run the same fill both ways on Grade 10’s temple:

from collections import dequefrom pixels import show_frames picture = [    "....................",    ".........##.........",    "........####........",    "......########......",    ".......#....#.......",    "......########......",    "....############....",    "......#......#......",    "......#......#......",    "....############....",    "..################..",    "....#..........#....",    "....#..........#....",    "..################..",    "..#..............#..",    "####################",] def fill_steps(picture, r, c, take):    """Unit 2's loop fill, with a stack or a queue: a picture per square."""    grid = [list(row) for row in picture]    to_do = deque([(r, c)])    frames = []    most = 1    while to_do:        if take == "stack":            r, c = to_do.pop()             # the newest square        else:            r, c = to_do.popleft()         # the oldest square        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):            continue        if grid[r][c] != ".":            continue        grid[r][c] = "o"        to_do.extend([(r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c)])        most = max(most, len(to_do))        frames.append([row.copy() for row in grid])    return frames, most for take in ["stack", "queue"]:    frames, most = fill_steps(picture, 1, 1, take)    print(f"{take}: {len(frames)} squares, at most {most} on the list")    show_frames(frames, {"#": "black", ".": "white", "o": "steelblue"})

stack: 160 squares, at most 248 on the listqueue: 160 squares, at most 44 on the list

Picture

Only lines 31 and 33 differ. A stack gives depth-first order, a queue breadth-first; the deque does both quickly, which a list’s pop(0) doesn’t.

A queue in a fixed number of places

Some queues live in memory of a fixed size: a keyboard’s small store of key presses, or a printer’s list of jobs. They are often kept in a circular queue (or ring buffer): a list of a fixed number of places that the queue goes round and round in. Two numbers say where it is: front, the place of the next item to leave, and count, how many items are waiting. The back is front + count, and when that runs off the end of the list it wraps round to place 0, with % (the remainder, Grade 8). Nothing ever moves; only the two numbers change.

A Python list keeps its items side by side in memory, in one long row of places, like seats in a cinema row. (Strictly, it keeps the arrows to its items there, as Unit 1 showed, all the same size.) That is what makes marks[500] instant: the computer works out where place 500 is from where the row starts. But it is also what makes adding or removing at the front slow: everyone in the row must shift one seat.

There is another way to keep things in order. Think of a treasure hunt at a school fair. You don’t get a list of all the places; each clue only tells you where the next clue is. The clues can be hidden anywhere, and to add a new clue at the start, you just write one new clue that points to the old first one. Nothing else moves.

A linked list is made of small objects called nodes. Each node holds a value and a reference to the next node, its link. The list itself only needs to know its first node, the head. The last node’s link is None: there is no next. Figure 3.4 shows both ways.

In Python, a node is an object of a tiny class, and its link is an attribute that refers to another node. Unit 1 showed that a name or an attribute never holds an object, only an arrow to it, and that is exactly what a link is.

Two moves are worth remembering. Adding at the front is head = Node(value, head): the new node’s link is the old head, and the new node becomes the head. Walking the list is node = node.next in a loop until node is None. Every program that uses a linked list is built from these two.

A linked list class

class Node:    def __init__(self, value, next=None):        self.value = value        self.next = next  class LinkedList:    def __init__(self):        self.head = None        self._size = 0     def push_front(self, value):        self.head = Node(value, self.head)        self._size = self._size + 1     def find(self, value):        """The position of value, counting from 0, or -1 if it isn't there."""        node = self.head        position = 0        while node is not None:            if node.value == value:                return position            node = node.next            position = position + 1        return -1     def __len__(self):        return self._size     def __str__(self):        parts = []        node = self.head        while node is not None:            parts.append(str(node.value))            node = node.next        return " → ".join(parts)  route = LinkedList()for stop in ["Ratnapark", "Thapathali", "Kupondole", "Jawalakhel", "Lagankhel"]:    route.push_front(stop)print(route)print(len(route), "stops; Kupondole is stop", route.find("Kupondole"))

Lagankhel → Jawalakhel → Kupondole → Thapathali → Ratnapark5 stops; Kupondole is stop 2

The class keeps a count, _size, so that len() is instant instead of walking the whole list. find() must walk: a linked list can’t jump to a position, because nothing says where node 2 is except node 1’s link. Reaching the item at position k takes k steps.

Front of a list, front of a linked list

Now compare adding 20,000 items at the front, one at a time, to a Python list (insert(0, …), which moves every item already there) and to a linked list (one new node each time).

import time  class Node:    def __init__(self, value, next=None):        self.value = value        self.next = next  for n in [10000, 20000, 40000]:    items = []    start = time.perf_counter()    for i in range(n):        items.insert(0, i)             # every item already there moves    list_time = time.perf_counter() - start     head = None    start = time.perf_counter()    for i in range(n):        head = Node(i, head)           # one new node, nothing moves    linked_time = time.perf_counter() - start     print(f"{n:>6} items: list {list_time * 1000:7.1f} ms, linked list {linked_time * 1000:6.1f} ms")

Run it a few times. The list’s time grows about four times for each doubling (quadratic), the linked list’s about twice (linear). But notice something else: for small numbers the list may win, because moving a row of items in memory is one fast job for the processor, while making a Python object for each node takes time too. Counting steps tells you how the work grows; only timing tells you which is faster at the size you really have. Real programmers do both.

Queues and stacks from linked nodes

A linked list makes a fine stack: push and pop at the head, both one step. With a second reference to the tail, the last node, it makes a fine queue too: enqueue at the tail and dequeue at the head, each one step, and no item ever moves. (Python’s deque is built in a similar way: a chain of blocks, each holding up to 64 items, linked both ways, so that both of its ends are quick.)

After the dequeue, nothing points to the node for token 101: not the queue, not another node. It fades away in the widget. Python’s garbage collection (Unit 1) will free its memory.

What a linked list is good for

In Python you will seldom write a linked list for real work: lists and deques are written in C inside Python and are very fast. But linked structures are everywhere underneath. A music player’s playlist, with next and previous, is naturally a doubly linked list, whose nodes have links both ways. The trees later in this unit are linked structures with two links per node. And every time you follow a reference from one object to another, as the bus route of Unit 1 did, you are walking links.

In Grade 9 you learned that a dictionary doesn’t search: from the key itself, it works out where the value is kept, by hashing, an idea Hans Peter Luhn wrote down at IBM in 1953. Now you can build one.

A hash table is a list of a fixed number of places called buckets. To store a key and its value:

1. Work out a whole number from the key with a hash function. Ours adds up the codes of the key’s letters (ord(), Grade 9): “Sita” is 83 + 105 + 116 + 97 = 401.
2. Turn that number into a bucket number: the remainder when it is divided by the number of buckets. With 8 buckets, 401 % 8 = 1, so Sita goes in bucket 1.
3. Put the key and its value in that bucket.

To find Sita again, do the same sum, go straight to bucket 1, and look only there. However many keys the table holds, a look-up only ever looks in one bucket.

What if two keys land in the same bucket? With 8 buckets, “Pasang” (602) and “Bikash” (594) both go in bucket 2. This is a collision, and it can’t be avoided: there are far more possible keys than buckets. The simplest answer, chaining, lets each bucket hold a short list of the pairs that landed in it. A look-up then checks the few keys in its bucket, one by one.

class HashTable:    """A dictionary of our own: buckets, each a list of (key, value) pairs."""     def __init__(self, buckets=8):        self._buckets = [[] for i in range(buckets)]     def _bucket(self, key):        code = sum(ord(ch) for ch in key)          # our own simple hash        return self._buckets[code % len(self._buckets)]     def put(self, key, value):        bucket = self._bucket(key)        for i in range(len(bucket)):            if bucket[i][0] == key:                bucket[i] = (key, value)           # a key already there: change it                return        bucket.append((key, value))                # a new key: add it     def get(self, key):        for k, v in self._bucket(key):             # look only in this key's bucket            if k == key:                return v        raise KeyError(key)  phones = HashTable()phones.put("Sita", "9841000011")phones.put("Ramesh", "9851000022")phones.put("Pasang", "9861000033")phones.put("Gita", "9801000044")phones.put("Bikash", "9841000055")print(phones.get("Bikash"))for number, bucket in enumerate(phones._buckets):    print(number, bucket)

98410000550 [('Ramesh', '9851000022')]1 [('Sita', '9841000011')]2 [('Pasang', '9861000033'), ('Bikash', '9841000055')]3 []4 []5 [('Gita', '9801000044')]6 []7 []

(The phone numbers are made up.) To find Bikash, get() worked out bucket 2 and compared two keys. It never looked at Sita, Ramesh or Gita.

Keeping the buckets short

A look-up is quick only while the buckets are short. The number of keys divided by the number of buckets is the load factor: 5 keys in 8 buckets is a load factor of 0.625. As keys are added the load factor rises and the buckets get longer, so a hash table grows: when the load factor passes a limit, it makes a table with about twice as many buckets and puts every key into it again, each in its new bucket. That one step is slow, but like a list’s append it happens rarely, so on average adding a key stays constant time. Python’s own dictionaries grow when they are about two-thirds full. They also handle collisions the other way, a cousin of Gene Amdahl’s “try the next bucket along” (Grade 9): instead of a list in each bucket, a key whose bucket is taken tries other buckets, in an order worked out from its hash, until it finds a free one.

With a good hash function and short buckets, finding, adding and changing a key take O(1) on average: a few steps, whether the table has ten keys or ten million. That is the answer to Grade 9’s question. In the worst case, though, every key lands in one bucket, and a look-up becomes a linear search through all of them.

Why a dictionary’s keys must not change

Suppose you could use a list as a key, seats[["Kathmandu", "Pokhara"]] = 40, and then changed the list to ["Kathmandu", "Chitwan"]. Its hash would change, so a look-up would go to a different bucket, while the pair is still sitting in the old one. The dictionary would lose it. So Python’s own types whose value can change (lists, dictionaries, sets) can’t be keys, and those whose value can’t change after they are made can: numbers, strings, tuples of those. A list can’t be a key:

seats = {}seats[["Kathmandu", "Pokhara"]] = 40

Traceback (most recent call last):  File "main.py", line 2, in <module>    seats[["Kathmandu", "Pokhara"]] = 40    ~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

A value Python can hash is called hashable. Use a tuple, which can’t change: seats[("Kathmandu", "Pokhara")] = 40 works. (Objects of your own classes, from Unit 1, can be keys too: unless the class says otherwise, Python hashes an object by which object it is, never by its attributes, so changing an attribute doesn’t move it to another bucket.) A set is a hash table too, of keys with no values, which is why card in valid_cards is quick for a set and slow for a list, and why a set can’t hold lists either.

A dictionary finds Sita’s phone number at once, but it can’t list the phone book in alphabetical order, or find everyone whose name starts with “Pa”. A sorted Python list can: binary search (Grade 8) finds a name in about log₂ n looks. But adding a new name to a sorted list means moving every name after it, which is slow for a big list. A binary search tree does both: it finds a key in a few looks, and a new key can be added without moving anything.

In Grade 10 you met trees: a root, children, parents, leaves, and no loops. A binary tree is a tree in which each node has at most two children, called its left and right child. A binary search tree (BST) is a binary tree with one rule at every node:

• every key in its left subtree (the left child and everything below it) is smaller than the node’s key;
• every key in its right subtree is bigger.

To find a key, start at the root and compare. Smaller: go left. Bigger: go right. Equal: found. Fall off the bottom (None): it isn’t there. Each comparison takes you one level down, so a search takes at most as many looks as the tree has levels, its height. To add a key, search for it, and put a new node where the search fell off.

Here is a BST in Python, as a phone book. Each node is an object with a key, a value and two links; put() and get() walk down with a loop, and get() counts its looks.

class Node:    def __init__(self, key, value):        self.key = key        self.value = value        self.left = None        self.right = None  class SearchTree:    """A phone book kept as a binary search tree."""     def __init__(self):        self.root = None     def put(self, key, value):        if self.root is None:            self.root = Node(key, value)            return        node = self.root        while True:            if key == node.key:                node.value = value                 # already there: change it                return            if key < node.key:                if node.left is None:                    node.left = Node(key, value)   # fell off: put it here                    return                node = node.left            else:                if node.right is None:                    node.right = Node(key, value)                    return                node = node.right     def get(self, key):        node = self.root        looks = 0        while node is not None:            looks = looks + 1            if key == node.key:                return node.value, looks            node = node.left if key < node.key else node.right        return None, looks     def in_order(self):        names = []        def visit(node):            if node is not None:                visit(node.left)                   # everything smaller first                names.append(node.key)                visit(node.right)                  # then everything bigger        visit(self.root)        return names  book = SearchTree()for name in ["Mina", "Dawa", "Sita", "Bimal", "Hari", "Pemba", "Tara"]:    book.put(name, "98" + str(len(name)) * 8)print(book.in_order())print(book.get("Pemba"))print(book.get("Kamala"))

['Bimal', 'Dawa', 'Hari', 'Mina', 'Pemba', 'Sita', 'Tara']('9855555555', 3)(None, 3)

(The numbers are made up from the names’ lengths.) Mina was added first, so she is the root. Pemba is found in 3 looks: Mina, then right to Sita, then left to Pemba. Kamala isn’t there: Mina, left to Dawa, right to Hari, and Hari has no right child.

in_order() lists the names in alphabetical order, though they were added in a jumble. It is recursive (Unit 2): to list a tree in order, list its left subtree in order, then the root, then its right subtree in order. The base case is an empty subtree, None, which lists nothing. Visiting a tree’s nodes like this is called an in-order traversal, and it gives the keys of any BST in sorted order. Two other orders visit every node too: a pre-order traversal visits each node before its subtrees, and a post-order traversal after them. You will try both in the exercise (question m).

Figure 3.5 shows the tree the program built.

When a tree leans

In a well-shaped tree each level holds twice as many nodes as the one above: 1, 2, 4, 8… A tree of 15 nodes can be 4 levels high, 1,023 nodes 10 levels, a million nodes about 20. So a search takes about log₂ n looks, like binary search: O(log n).

But the shape depends on the order the keys arrive. Add keys that are already sorted, and each new key is bigger than all before it, so it always goes right. The tree becomes one long line, really a linked list, with a height of n, and a search is linear. Run this to see the heights:

import random  class Node:    def __init__(self, key):        self.key = key        self.left = None        self.right = None  def build(keys):    """A BST of the keys, added in this order. Gives back its height."""    root = Node(keys[0])    height = 1    for key in keys[1:]:        node = root        level = 1        while True:            level = level + 1            if key < node.key:                if node.left is None:                    node.left = Node(key)                    break                node = node.left            else:                if node.right is None:                    node.right = Node(key)                    break                node = node.right        height = max(height, level)    return height  random.seed(3)for n in [100, 1000, 3000]:    keys = list(range(n))    random.shuffle(keys)    print(f"{n:>5} keys: height {build(keys):>3} in a random order, {build(sorted(keys)):>4} in sorted order")

  100 keys: height  14 in a random order,  100 in sorted order 1000 keys: height  20 in a random order, 1000 in sorted order 3000 keys: height  31 in a random order, 3000 in sorted order

In a random order the height stays small: log₂ 3,000 is about 11.6, and the random tree is 31 levels high, under three times that (a random order usually gives about that). Sorted, the height is n: 3,000. Notice that build() walks down with a loop, not by recursion: on the lopsided tree of 3,000 levels, a recursive walk would pass Python’s limit of about 1,000 waiting calls (Unit 2).

Real programs don’t trust luck. A balanced search tree checks its shape after each change and, when one side gets too deep, turns a few nodes round (a rotation) to keep the height near log₂ n, whatever order the keys arrive in.

At a hospital’s emergency department, patients don’t wait in the order they came. A nurse looks at each new patient and decides how urgent they are; a man who can’t breathe is seen before a girl with a sprained wrist who came an hour earlier. This is called triage. Among patients who are equally urgent, the one who came first goes first.

A priority queue is a queue in which every item has a priority, and the item taken out next is always the one with the highest priority, not the oldest. Its operations are: add an item with its priority, and take the item with the highest priority. Here we write the priority as a number, 1 for the most urgent, so “highest priority” means the smallest number.

How could you build one?

• An unsorted list: adding is quick (append), but taking the most urgent means looking at every patient. O(n).
• A sorted list: taking is quick (the front), but adding a patient means finding their place and moving everyone behind. O(n).
• A heap: both take only O(log n) steps. For a thousand patients, about 10 steps instead of about 1,000.

A heap is a binary tree with two rules:

1. Its shape is complete: every level is full, except perhaps the last, which is filled from the left with no gaps.
2. The heap rule: every parent is at least as urgent as its children (its number is smaller or equal). So the most urgent item of all is always at the root.

A heap is not sorted. The heap rule says nothing about left against right, or about a node and its cousins: only that each parent comes before its own children. That is much less work to keep true than full order, and it is enough to find the most urgent at once.

A tree kept in a list

Because the shape is complete, a heap needs no links at all. Number the nodes level by level, left to right, from 0, and store them in a list in that order. Then the children of the node at position i are always at positions 2i + 1 and 2i + 2, and its parent at (i − 1) // 2. Figure 3.7 shows a heap both ways.

Adding and taking

• Add: put the new item at the end of the list, the next place in the bottom row. It may be more urgent than its parent; if so, swap them, and keep swapping it upwards while it is more urgent than its parent. This is called sifting up. It stops at the root at the latest.
• Take: the most urgent item is at position 0. Take it out, move the last item into position 0 (so the shape stays complete), then sift down: while it is less urgent than the more urgent of its children, swap it with that child.

Each sift moves one level per swap, and a heap of n items has about log₂ n levels, so both operations are O(log n).

Here is a triage queue as a class, with its own sift up and sift down. Each item is a tuple (urgency, token, name). Python compares tuples item by item, first the urgency and then, for a tie, the token number, so among equally urgent patients the one with the lower token, who came first, goes first.

class TriageQueue:    """Patients by urgency (1 is the most urgent), kept as a heap in a list."""     def __init__(self):        self._heap = []            # tuples (urgency, token, name)        self._token = 0     def arrive(self, name, urgency):        self._token = self._token + 1        self._heap.append((urgency, self._token, name))        i = len(self._heap) - 1        while i > 0:                                   # sift up            parent = (i - 1) // 2            if self._heap[i] < self._heap[parent]:                self._heap[i], self._heap[parent] = self._heap[parent], self._heap[i]                i = parent            else:                break     def next_patient(self):        top = self._heap[0]        last = self._heap.pop()        if self._heap:            self._heap[0] = last                       # the last item to the top            i = 0            while True:                                # sift down                first = i                for child in [2 * i + 1, 2 * i + 2]:                    if child < len(self._heap) and self._heap[child] < self._heap[first]:                        first = child                if first == i:                    break                self._heap[i], self._heap[first] = self._heap[first], self._heap[i]                i = first        return top     def __len__(self):        return len(self._heap)  er = TriageQueue()er.arrive("Ram, sprained wrist", 4)er.arrive("Sunita, high fever", 3)er.arrive("Bishnu, deep cut", 2)er.arrive("Maya, can't breathe", 1)er.arrive("Kiran, broken arm", 2)print(er._heap[0])while len(er) > 0:    print(er.next_patient())

(1, 4, "Maya, can't breathe")(1, 4, "Maya, can't breathe")(2, 3, 'Bishnu, deep cut')(2, 5, 'Kiran, broken arm')(3, 2, 'Sunita, high fever')(4, 1, 'Ram, sprained wrist')

Ram came first but is seen last. Bishnu and Kiran are equally urgent; Bishnu, with the lower token, came first and is seen first.

Python has a heap ready made, in its heapq library. It keeps a heap in an ordinary list, with the smallest item at position 0:

import heapq waiting = []heapq.heappush(waiting, (4, 1, "Ram"))heapq.heappush(waiting, (3, 2, "Sunita"))heapq.heappush(waiting, (2, 3, "Bishnu"))heapq.heappush(waiting, (1, 4, "Maya"))print(waiting)print(heapq.heappop(waiting))print(waiting)

[(1, 4, 'Maya'), (2, 3, 'Bishnu'), (3, 2, 'Sunita'), (4, 1, 'Ram')](1, 4, 'Maya')[(2, 3, 'Bishnu'), (4, 1, 'Ram'), (3, 2, 'Sunita')]

After the pop, look at the list: Ram, urgency 4, comes before Sunita, urgency 3. The list isn’t sorted, but it is a heap: Bishnu at position 0 comes before both of his children, Ram at position 1 and Sunita at position 2.

Heaps are used wherever “the most urgent next” matters: a computer’s operating system choosing which waiting job to run (Unit 4), a game deciding which event happens next, and a map app finding the nearest place still to visit when it plans a route, which you will do in Grade 12 with Dijkstra’s algorithm. A heap also sorts: put every item in, then take them out, smallest first. That is heapsort, published in 1964 by J. W. J. Williams, who was working for the British computer maker Elliott Brothers, in Borehamwood near London; his short paper was the first to describe the binary heap. Heapsort is a faster version of a simpler sort, selection sort, which you will write and compare in question n of the exercise.

Every structure in this unit is fast at some things and slow at others. None is best for everything. So choose a data structure the way an engineer chooses a vehicle: not “which is best?” but “what must it do most?” A motorbike is best for one person in traffic, a truck for cement, a bus for forty people.

Here is the method:

1. List the operations the program needs: find by key, find by position, add, remove, take the oldest, take the newest, take the most urgent, go through in order.
2. Say how often each is done. A phone book is looked up a hundred times for every new name added.
3. Choose the structure that makes the most frequent operations fast, using the table below.
4. Test it: check that it gives the right answers on a few chosen cases, including the awkward ones (empty, one item, a key that isn’t there), and time it on data as big as the real data, because steps tell you how the work grows, and only a clock tells you the real speed.

(For a dictionary, “O(1)” is on average, with a good hash function; adding at the end of a list is O(1) amortized, as the fact about appending explained; a plain, unbalanced search tree can be O(n), as you saw.)

A phone book, timed three ways

Here is step 4 for a real case: a phone book of 20,000 names kept as a list of pairs, as a search tree, and as a dictionary, with the same 200 names looked up in each. The names were added in a random order, so the tree is bushy.

import randomimport time  class Node:    def __init__(self, key, value):        self.key = key        self.value = value        self.left = None        self.right = None  class SearchTree:    def __init__(self):        self.root = None     def put(self, key, value):        if self.root is None:            self.root = Node(key, value)            return        node = self.root        while True:            if key < node.key:                if node.left is None:                    node.left = Node(key, value)                    return                node = node.left            else:                if node.right is None:                    node.right = Node(key, value)                    return                node = node.right     def get(self, key):        node = self.root        while node is not None:            if key == node.key:                return node.value            node = node.left if key < node.key else node.right        return None  def list_get(key):    for k, v in pairs:        if k == key:            return v    return None  random.seed(5)names = [f"Person {i:05}" for i in range(20000)]random.shuffle(names)pairs = [(name, f"98{random.randint(10000000, 99999999)}") for name in names]tree = SearchTree()for name, phone in pairs:    tree.put(name, phone)book = dict(pairs)wanted = random.sample(names, 200) for label, get, rounds in [("list", list_get, 1), ("search tree", tree.get, 100), ("dictionary", book.get, 1000)]:    for name in wanted:        assert get(name) == book[name]     # a test: every answer must be right    start = time.perf_counter()    for _ in range(rounds):        for name in wanted:            get(name)    ms = (time.perf_counter() - start) / (rounds * len(wanted)) * 1000    print(f"{label:>12}: {ms:9.5f} ms a look-up")

assert is a test written into the program: if the condition is ever false, the program stops with an AssertionError, so a wrong answer can’t hide behind a good time. The faster structures are timed over many rounds of the same 200 names, because in a browser Python’s clock may tick only every tenth of a millisecond: a single round of dictionary look-ups would finish between two ticks. Press Run. On a laptop, in its browser, one run gave:

The tree is about two hundred times faster than the list, and the dictionary about ten times faster again. Your times will differ, and the tree’s jump about most from run to run, but the order won’t. Now the other half of the decision: this phone book must also be printed in alphabetical order once a day. The tree gives that for free with an in-order traversal; the dictionary must sort its 20,000 names, which takes a few milliseconds. For a phone book, that is nothing, so the dictionary wins. For a program that answers “every name between Pa and Pe” all day long, the tree would.

Choose one, and build it with the structures of this unit, as classes.

• An editor with undo and redo. Start from the Editor class. Store each change as a small note (what was typed or deleted, and where) instead of a copy of the whole text, so a long document stays small. Add a limit: keep only the last 50 changes, and drop the oldest when there are more (which structure drops from the bottom of a stack quickly?).
• A hospital token system. Patients take tokens and a nurse gives each an urgency from 1 to 4. The doctor’s screen always shows the next patient: the most urgent, and among equals the earliest. Add a check that nobody waits for ever: once a patient has waited for 30 patients to be seen before them, raise their urgency by one.
• A bracket checker for Python. Read a Python program (a file shown on the page, as in Grade 10) and report every bracket that doesn’t match, with its line number and the bracket it should have been. Ignore brackets inside strings.
• A phone book, three ways. Load at least 10,000 names, and time looking up, adding and listing in order with a list, your search tree and a dictionary. Then add the names in alphabetical order and time the tree again. Write a short report: which would you choose for a school’s contact list, and why?

1. Write down the operations your program needs and how often each happens.
2. Choose a structure for each, and say why in a sentence, using what each operation costs.
3. Build one class at a time, and test each method on small cases first: empty, one item, the item that isn’t there.
4. Time it on data as big as the real thing, with time.perf_counter(), a few runs each.
5. Show and explain: show your class beside its test results and your timings, and explain one choice you would make differently if the program were used ten times as often.

All of these run on this page’s programs, even on a phone: edit a program and press Run. A long program is easier on a computer, in a Python editor (Grade 10).