Trees, Binary Search Trees, Balancing, Heaps and Priority Queues

Last week's hash table finds an exact key almost instantly, but it has no idea what order its keys are in. This week we meet two structures that do. A binary search tree keeps everything sorted while you keep adding to it. A heap always knows which item is the smallest, so it can tell you "who's next." By Thursday you will be able to build either one.

Session planHow we will spend the two sessions

Section 1Keeping things in order

Notes 06 ended with a list of things a hash table is bad at: listing keys in sorted order, finding everything in a range, finding the smallest or the nearest key, and promising that every operation is fast. All four are questions about order, and a hash table throws order away on purpose — it scatters keys into random-looking buckets.

Think of an old paper phone book. It is sorted by name, and that one fact makes lots of questions easy. Find "Miller": flip to M. Everyone named Miller: they are all together on one page. The name right after "Miller": look at the next line. A hash table is more like a coat check with scrambled ticket numbers. It is perfect for "give me coat 47," and useless for "give me every coat belonging to someone named M-something."

So why not just keep a sorted Python list? Finding things in it is fast with binary search — the halving trick from Notes 02 and 03. The trouble is adding things. To put a new name in the middle of a sorted list, everything after it has to shift over one spot to make room. With a million names, one insert can mean moving a million names. It is like adding one new person to a printed phone book: you have to reprint the whole thing.

Section 2Tree words

You have seen trees all your life: a family tree, or a company's org chart with the boss at the top and the people who report to them below. Computer scientists draw trees the same way — upside down compared with a real tree, with the "root" at the top.

Here are the words we will use all week. Each one is just a family-tree word.

• A node is one box in the tree. It holds one key (and maybe a value stored with it, like in a dict).
• The root is the node at the very top — the boss in the org chart. Every tree has exactly one (unless it is empty).
• The nodes directly below a node are its children, and it is their parent. Every node except the root has exactly one parent.
• A leaf is a node with no children — the bottom of the org chart.
• A subtree is a node together with everything below it. Each child of a node starts its own little tree. That is what makes trees so natural for recursion (Notes 03): a tree is a root plus smaller trees.
• The height of a tree is the number of levels it has: count the nodes on the longest path from the root down to a leaf. The tree above has height 3. A lone root has height 1, and an empty tree has height 0. (Some books count the links between nodes instead, which gives one less. The idea is the same.)
• A binary tree is a tree where every node has at most two children, called its left child and right child. "Binary" just means "two." Everything this week is a binary tree.

Remember the word height above all the others. Almost every cost this week comes down to "how tall is the tree?"

Section 3Binary search trees: the higher-or-lower game

Play a game with a friend. They think of a number from 1 to 100, and you guess. After each guess they say "higher," "lower," or "got it." The smart first guess is 50: whatever they answer, you have thrown away half the numbers. Then 25 or 75, and so on. You will always win in 7 guesses or fewer. That is binary search from Notes 02.

A binary search tree is that game, frozen into a structure. Each node is a guess. Its left side holds everything lower; its right side holds everything higher.

Searching: higher or lower

To find a key, start at the root and play the game:

• If the key equals this node's key, you found it.
• If the key is smaller, go left ("lower").
• If the key is bigger, go right ("higher").
• If you try to step to a child that isn't there, you have "fallen off" the tree: the key is not in it.

Here is a search for 65 in the starter tree of Demonstration 1 below:

Inserting: search, then fill the gap

Inserting is searching. Search for the new key. If you find it, it is already there (a dict would just update its value). If you fall off the tree, the empty spot where you fell off is exactly where the new key belongs. Put a new leaf there. Done — nothing else in the tree moves.

Why is that spot the right one? Every step of the search compared the new key with a node and went the correct way, so the new leaf is on the correct side of every node above it. The rule still holds everywhere.

How many steps?

Each check moves you one level down. So a search or an insert takes at most as many checks as the tree has levels — its height. In a nicely bushy tree, each level holds twice as many nodes as the level above it: 1, 2, 4, 8, 16… So 10 levels hold about a thousand keys, 20 levels hold about a million, and 30 levels about a billion. In Notes 02's language, a bushy tree gives logarithmic time — Θ(log n), "grows very slowly." Hold on to the word bushy; Section 6 shows what happens when a tree isn't.

Section 4What order buys you

So far a BST does what a hash table does, only a bit slower. Here is the payoff: everything a hash table can't do.

Sorted order, for free: the in-order walk

To list every key from smallest to largest, visit each node like this: first everything on its left, then the node itself, then everything on its right. Do the same thing inside each subtree. This is called an in-order walk.

Why does it come out sorted? Everything on a node's left is smaller than it, so it should come out first — and it does. Everything on its right is bigger, so it should come out after — and it does. The same is true inside every subtree, all the way down. It is like reading a bookshelf from left to right.

The walk visits each node once, so listing n keys takes time proportional to n — linear. Compare the hash table: to list its keys in order, it must pull them all out and sort them every time you ask.

Smallest and largest

The smallest key: start at the root and keep going left until there is no left child. The largest: keep going right. Each takes at most "height" steps. A hash table would have to check every key.

The next one up, and ranges

"What is the cheapest item that costs at least $20?" is a search for 20 that remembers the best candidate it passed on the way: every time you go left at a node, that node is bigger than 20, so it is a candidate. "Every key between 30 and 60" is an in-order walk that skips whole branches that can't contain anything in the range — if a node is smaller than 30, nothing on its left can be in range, so don't even go there. The work is about the height plus the number of keys you report. That is the leaderboard question from Notes 06's last self-check.

Here is a plain BST in Python with all of this. Read it next to the rules above; every method is a few lines.

class Node:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.left = None       # smaller keys live down here
        self.right = None      # bigger keys live down here


class BST:
    """A plain (unbalanced) binary search tree: key → value, kept in order."""

    def __init__(self):
        self.root = None
        self.size = 0

    def put(self, key, value=None):
        if self.root is None:
            self.root = Node(key, value)
            self.size = 1
            return
        node = self.root
        while True:
            if key == node.key:              # already here: just update
                node.value = value
                return
            if key < node.key:               # lower: go left
                if node.left is None:
                    node.left = Node(key, value)   # fell off: the new leaf goes here
                    break
                node = node.left
            else:                             # higher: go right
                if node.right is None:
                    node.right = Node(key, value)
                    break
                node = node.right
        self.size += 1

    def _find(self, key):
        node = self.root
        while node is not None and node.key != key:
            node = node.left if key < node.key else node.right
        return node                         # None means "fell off"

    def get(self, key):
        node = self._find(key)
        if node is None:
            raise KeyError(key)
        return node.value

    def __contains__(self, key):           # makes  key in tree  work
        return self._find(key) is not None

    def __len__(self):
        return self.size

    def in_order(self):
        """Every key, smallest to largest: left, node, right."""
        def walk(node):
            if node is not None:
                yield from walk(node.left)
                yield node.key
                yield from walk(node.right)
        return walk(self.root)

    def minimum(self):
        if self.root is None:
            raise ValueError("empty tree")
        node = self.root
        while node.left is not None:          # keep going left
            node = node.left
        return node.key

    def keys_between(self, lo, hi):
        """Every key with lo <= key <= hi, in sorted order."""
        out = []
        def walk(node):
            if node is None:
                return
            if lo < node.key:                 # something in range might be on the left
                walk(node.left)
            if lo <= node.key <= hi:
                out.append(node.key)
            if node.key < hi:                 # something in range might be on the right
                walk(node.right)
        walk(self.root)
        return out


t = BST()
for k in [50, 30, 70, 20, 40, 60, 85]:
    t.put(k)
print(list(t.in_order()))       # [20, 30, 40, 50, 60, 70, 85] — sorted, no sort() needed
print(t.minimum())               # 20
print(t.keys_between(35, 65))    # [40, 50, 60]
print(45 in t, len(t))           # False 7

Section 5Deleting a key

Deleting is the one BST operation that needs some thought, because removing a node can leave a hole in the middle of the tree. First find the node with the usual higher-or-lower search. Then there are three cases, from easy to less easy:

1. It's a leaf (no children). Just remove it. Nobody below it needs a new parent.
2. It has one child. Let that child move up and take its place, bringing its whole subtree along. Like a manager leaving: their only team member gets promoted into their chair. The rule still holds, because that whole subtree was already on the correct side of everything above.
3. It has two children. Now neither child can simply move up. Instead, find the key that should come right after it in sorted order — its successor. The successor is the smallest key in the node's right subtree: go right once, then left as far as you can. Copy the successor's key into the node being deleted, then delete the successor from the right subtree. That second delete is always easy: the successor has no left child (Check yourself 3!), so it is case 1 or case 2.

Why is the successor a safe replacement? It is bigger than everything on the left (it came from the right side) and smaller than everything else on the right (it was the smallest there). It fits the gap exactly. Using the predecessor — the largest key on the left — works just as well; you only have to pick one.

Some things to try, in order:

1. Search for 65. Follow the numbered steps: right, left, right, found — 4 checks.
2. Search for 37. The search falls off below 35. Now Insert 37 and see it appear in exactly that spot.
3. Press Smallest and Largest. Notice they just slide down the left and right edges.
4. Delete 20 (a leaf), then 60 (one child: 65 moves up), then 50, the root (two children: its successor 65 takes its place).
5. Press In order: 1, 2, 3 … and look at the shape. Then try Middle-first order and Random order with the same 15 keys. Compare the heights. Section 6 is about what you just saw.

Section 6The lopsided tree

Here is the catch with plain BSTs. Insert 1, then 2, then 3, and so on up to 15. Each new key is bigger than everything already there, so it always goes right, and right, and right. The "tree" turns into a stick: 15 levels tall, one node per level. Searching for 15 takes 15 checks. That is a linked list wearing a tree costume — exactly like the all-in-one-bucket hash table from Notes 06, Section 7.

The shape of a BST depends only on the order the keys arrive in. The same 15 keys can make a perfect bushy tree of height 4 (middle key first, then the middles of each half) or a stick of height 15 (sorted order). Random order usually lands in between, a bit worse than perfect.

And sorted input is not a rare accident. Real data arrives in order all the time: records sorted by date, student IDs handed out in sequence, a file that someone already sorted alphabetically. A plain BST is at its very worst on exactly the data you are most likely to feed it.

Section 7Balancing with rotations

We can't control the order data arrives in. So instead, the tree has to fix its own shape as it goes. A balanced (or self-balancing) search tree checks itself after every insert and delete, and if it has started to lean too far one way, it straightens itself out on the spot. The goal is simple: keep the height small — close to the bushy best — no matter what order the keys come in.

The rotation

The tool for straightening is called a rotation. Picture a hanging mobile, or a tree drawn on a string, that leans badly to the left. Pick it up by a different node — one lower down on the heavy side — and it falls into a new, more even shape. Nothing is added or removed; a couple of nodes just swap who is on top.

The smallest example: insert 3, 2, 1. You get a stick leaning left. Rotate right at 3: 2 moves up to the top, 3 moves down to become 2's right child, and 1 stays where it was, on 2's left.

In a bigger tree, the two nodes have other subtrees hanging off them. Here is the general picture. The triangles A, B and C stand for whole subtrees (maybe empty, maybe huge):

Two things make rotations the perfect repair tool:

• They never break the BST rule. Read the picture left to right: A, x, B, y, C, both before and after. The sorted order is untouched. B fits between x and y in both pictures, which is why it can switch parents safely.
• They are cheap. A rotation changes three links, no matter how big the tree is. That is constant time — it doesn't grow with the size.

Sometimes the lean has a bend in it — for example, insert 3, 1, 2: the tree goes left, then right (a zig-zag). One rotation at the top won't fix a bend. The fix is two rotations: first a small one at the lower node to straighten the bend into a plain stick, then the usual one at the top. This is called a double rotation. You can watch it in Demonstration 1: tick Keep it balanced, press Clear, and insert 3, 1, 2.

AVL trees: "never let the sides differ by more than one"

The oldest balanced tree is the AVL tree, named after its two inventors, Adelson-Velsky and Landis (1962). Its rule is easy to say:

Inserting into an AVL tree is a normal BST insert, followed by a walk back up the path you came down. At each node on the way up, update its height and check its lean. If the lean has hit +2 or −2, do a single or double rotation right there. That's all. Each fix is constant time, and the path is only "height" long.

The payoff: an AVL tree is never much taller than the perfect bushy tree — at most about one and a half times as tall. For a million keys that means under 30 levels, guaranteed, whatever order the keys arrive in. A search, insert or delete is logarithmic every time, not just on average. That is the "hard speed promise" from the end of Notes 06.

Try it: in Demonstration 1, press In order: 1, 2, 3 … to make the 15-level stick, then tick Keep it balanced. The same keys are inserted again in the same order, this time with rotations, and the tree comes out 4 levels tall — the best possible. Tick Show the lean to see every node's lean; with balancing on, none is ever outside −1 to +1.

Here is the core of an AVL tree in Python. The pieces are small: a height on every node, two rotations, and a rebalance step that runs at each node on the way back up.

class AVLNode:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.height = 1               # a lone node is one level tall


def height(node):
    return node.height if node is not None else 0

def update(node):
    node.height = 1 + max(height(node.left), height(node.right))

def lean(node):
    return height(node.left) - height(node.right)   # +2: too heavy on the left

def rotate_right(y):
    x = y.left
    y.left = x.right                  # the middle subtree B changes parent
    x.right = y
    update(y)                         # y is lower now: fix its height first
    update(x)
    return x                          # x is the new top of this subtree

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x)
    update(y)
    return y

def rebalance(node):
    update(node)
    if lean(node) > 1:                        # leaning left
        if lean(node.left) < 0:                # with a bend: straighten it first
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if lean(node) < -1:                       # leaning right: the mirror image
        if lean(node.right) > 0:
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node                                # fine as it is

def avl_insert(node, key, value=None):
    """Insert into the subtree rooted at node; return the subtree's new top."""
    if node is None:
        return AVLNode(key, value)           # fell off: new leaf
    if key < node.key:
        node.left = avl_insert(node.left, key, value)
    elif key > node.key:
        node.right = avl_insert(node.right, key, value)
    else:
        node.value = value                     # already here: just update
        return node
    return rebalance(node)                     # on the way back up: check and fix

def in_order(node):
    if node is not None:
        yield from in_order(node.left)
        yield node.key
        yield from in_order(node.right)


root = None
for k in range(1, 16):                       # 1..15 in order: a plain BST's worst case
    root = avl_insert(root, k)
print(height(root))                           # 4 — not 15
print(root.key)                               # 8 — the middle key ended up on top
print(list(in_order(root)) == list(range(1, 16)))   # True

Notice the pattern node.left = avl_insert(node.left, ...). A rotation can change which node sits at the top of a subtree, so every call returns the new top, and the parent re-attaches it. Forgetting to use the returned node is the most common AVL bug: the rotation happens, but the parent still points at the old top, and part of the tree disappears. Deleting from an AVL tree works the same way — the BST delete from Section 5, with rebalance called on the way back up.

Red-black trees, and what your language gives you

The other famous balanced tree is the red-black tree. Every node is painted red or black, and a few coloring rules keep the tree from getting too lopsided. Its rule is looser than AVL's — it allows a bit more lean — so it does fewer rotations when you insert and delete, at the cost of being slightly taller. Both keep every operation logarithmic. You do not need to know the coloring rules for this course.

• Java: TreeMap and TreeSet are red-black trees. (C++'s std::map usually is too.)
• Python: has no balanced search tree built in. The closest built-in tool is a sorted list kept in order with the bisect module: finding is fast, but every insert shifts everything after it, so inserting is linear. The popular add-on package sortedcontainers fills the gap; inside, it is a clever list of short sorted lists rather than a tree, but it does the same job.

Section 8Heaps: who's next?

Walk into a hospital emergency room. Patients are not seen in the order they arrived. A nurse sorts them by urgency — triage — and whoever is most urgent goes next, even if they walked in a minute ago. New patients keep arriving all evening, and each time a doctor is free, the question is the same: who is most urgent right now?

A full search tree could answer that, but it does far more work than needed: it keeps everyone in perfect order, when we only ever ask about the one at the front. A heap keeps just enough order to answer "who's next?" quickly, and nothing more. You met the heap briefly in heapsort, back in Notes 05; now we look at it properly.

The heap rule: a tournament bracket

Think of a sports tournament bracket. Each match has a winner, and the winner moves up a level. The champion sits at the very top, having beaten everyone below. In a heap, "winning" means "being smaller."

Compare that with the BST rule. A BST says "left is smaller, right is bigger" — a left-to-right order. A heap only says "parents beat children" — a top-to-bottom order. It says nothing about left versus right. Two siblings can be in either order, and a heap is not sorted. That looser rule is exactly what makes a heap cheaper to keep up.

A complete tree, stored in a plain list

A heap has one more rule about its shape: it is a complete tree. It fills up level by level, left to right, like seats in a theater filled row by row, with no gaps. Only the bottom row can be partly filled, and it fills from the left.

Because there are never any gaps, we don't need nodes and links at all. We can number the spots in reading order — the root is slot 0, its children are slots 1 and 2, the next row is 3, 4, 5, 6, and so on — and store the whole tree in an ordinary Python list. Moving around the tree becomes simple arithmetic:

In Python, "divide and round down" is //, so the parent is (i - 1) // 2. The heap is a tree in our heads and a list in memory. That makes heaps fast in practice, too: no node objects, no links to follow, just a list.

Push: add at the end, bubble up

To add a new item:

1. Put it in the first free slot — the end of the list. The tree is still complete.
2. It might be smaller than its parent, which breaks the heap rule. So compare it with its parent. If it is smaller, swap them. Repeat from its new spot. Stop when its parent is smaller or equal, or when it reaches the top.

This is called bubbling up (or "sifting up"). Like a new player who keeps winning matches and moving up the bracket until they meet someone better.

Pop: take the top, move the last item up, sink down

To remove the smallest item:

1. The smallest is the root, slot 0. Take it out. That leaves a hole at the top.
2. Move the last item in the list into the hole. (Taking the last item keeps the tree complete — no gap in the middle.)
3. That item is probably too big for the top. Compare it with its children. If either child is smaller, swap it with the smaller of the two. Repeat from its new spot. Stop when no child is smaller, or it reaches the bottom.

This is sinking down (or "sifting down"). Why the smaller child? That child is about to become the parent of the other one, so it has to be the smaller of the two, or the rule breaks again right away.

Both operations walk one path between the top and the bottom, so they take at most "height" swaps. And a complete tree is always as bushy as possible — no balancing needed, ever. A heap of a million items has 20 levels. Push and pop are logarithmic; peeking at the smallest is instant, because it is always in slot 0.

Some things to try:

1. Push 1. It lands in slot 7, then bubbles up past 9, 5 and 2 to the top: three swaps, one per level.
2. Push 50. It lands at the end and its parent is already smaller, so it stays: zero swaps.
3. Press Pop smallest a few times. Watch the last item jump to the top and sink back down. Look at the "Popped so far" list: it comes out in sorted order. That is heapsort from Notes 05 — push everything, then pop everything.
4. Tick Step by step and push or pop again, pressing Next step yourself. At each step, check the slot arithmetic in the box under the array.
5. Look at the array view at any moment. It is almost never sorted — and it doesn't need to be.

Section 9Priority queues in Python

A normal line at a store is a queue: first come, first served. A priority queue is a line where everyone has a priority number, and the most urgent goes first — the ER, or airport boarding by groups, where group 1 boards before group 2 no matter when they got to the gate. A priority queue needs just three operations:

• push — add an item with its priority;
• peek — look at the most urgent item without removing it;
• pop — remove and return the most urgent item.

"Priority queue" is the job; "heap" is the usual way to do the job. (A balanced BST could do it too, but a heap is simpler and faster.) Smaller numbers mean "more urgent" in a min-heap, so priority 1 beats priority 3.

Python's heapq

Python's built-in module heapq turns an ordinary list into a min-heap. There is no heap class — just functions that work on a list you own:

import heapq

er = []                                     # a plain list, used as a heap
heapq.heappush(er, (3, "sprained ankle"))     # (priority, patient)
heapq.heappush(er, (1, "heart attack"))
heapq.heappush(er, (2, "broken arm"))

print(er[0])                  # (1, 'heart attack') — peek: the top is slot 0
print(heapq.heappop(er))      # (1, 'heart attack')
print(heapq.heappop(er))      # (2, 'broken arm')
print(len(er))                # 1

nums = [9, 4, 7, 1, 8]
heapq.heapify(nums)            # rearrange an existing list into a heap, in place
print(nums[0])                # 1
print(heapq.nsmallest(3, [9, 4, 7, 1, 8]))   # [1, 4, 7]

Tuples compare item by item, so (1, "heart attack") comes before (3, "sprained ankle") because 1 < 3. That is how you attach a priority to anything: put the priority first.

Building our own

Want to write the heap yourself? Here it is — a short class, and every line is one of the steps from Section 8:

class MinHeap:
    """A min-heap stored in a plain list. Slot 0 is always the smallest."""

    def __init__(self):
        self.items = []

    def __len__(self):
        return len(self.items)

    def peek(self):
        if not self.items:
            raise IndexError("peek at empty heap")
        return self.items[0]

    def push(self, x):
        self.items.append(x)                      # 1. first free slot: the end
        self._bubble_up(len(self.items) - 1)      # 2. float it up

    def pop(self):
        if not self.items:
            raise IndexError("pop from empty heap")
        top = self.items[0]                      # 1. the smallest is on top
        last = self.items.pop()                   # 2. take the last item off the end
        if self.items:                            #    (if that was the only item, we're done)
            self.items[0] = last                  #    and put it in the hole at the top
            self._sink_down(0)                    # 3. let it sink
        return top

    def _bubble_up(self, i):
        a = self.items
        while i > 0:
            parent = (i - 1) // 2
            if a[i] < a[parent]:                   # smaller than its parent: swap up
                a[i], a[parent] = a[parent], a[i]
                i = parent
            else:
                break                             # parent is smaller or equal: done

    def _sink_down(self, i):
        a = self.items
        n = len(a)
        while True:
            left, right = 2 * i + 1, 2 * i + 2
            smallest = i
            if left < n and a[left] < a[smallest]:
                smallest = left
            if right < n and a[right] < a[smallest]:
                smallest = right
            if smallest == i:                     # no child is smaller: done
                return
            a[i], a[smallest] = a[smallest], a[i]  # swap with the SMALLER child
            i = smallest


h = MinHeap()
for x in [5, 2, 8, 1, 9]:
    h.push(x)
print(h.peek())                         # 1
print([h.pop() for _ in range(len(h))])   # [1, 2, 5, 8, 9] — sorted

Three details worth pointing at:

• pop handles the one-item heap. If the heap had a single item, self.items.pop() removes it and the list is empty; there is nothing to sink. Without the if self.items check, self.items[0] = last crashes on the empty list.
• _sink_down checks that each child exists (left < n, right < n) before looking at it. Near the bottom, a node may have one child or none.
• It works on anything comparable, including (priority, arrival_number, item) tuples — exactly like heapq.

Section 10Which structure?

You now have three structures for keys: the hash table (Notes 06), the balanced search tree and the heap. None of them is best at everything. Here is what each one is good at, in plain words:

"Instant" means constant time — it doesn't grow with the size. "Fast" means logarithmic — about 20 steps for a million keys, 30 for a billion. "Slow" means linear — it grows in step with the size. A simple way to choose: exact lookups only → hash table. Order, ranges or nearest → search tree. Only ever "the next most urgent" → heap.

Section 11Testing a structure like a pro

import heapq
import random


def check_bst(node, lo=None, hi=None):
    """True if every key below node is strictly between lo and hi."""
    if node is None:
        return True
    if lo is not None and node.key <= lo:
        return False
    if hi is not None and node.key >= hi:
        return False
    # everything on the left must stay below node.key; on the right, above it
    return check_bst(node.left, lo, node.key) and check_bst(node.right, node.key, hi)


def check_avl(node):
    """Return the true height; fail if any lean is outside -1..+1 or a height is stale."""
    if node is None:
        return 0
    hl = check_avl(node.left)
    hr = check_avl(node.right)
    assert abs(hl - hr) <= 1, f"node {node.key} leans too far"
    assert node.height == 1 + max(hl, hr), f"node {node.key} has a stale height"
    return 1 + max(hl, hr)


def check_heap(items):
    for i in range(1, len(items)):
        assert items[(i - 1) // 2] <= items[i], f"slot {i} is smaller than its parent"


def test_avl_random_and_sorted():
    for trial in range(100):
        keys = random.sample(range(10_000), 300)
        if trial % 10 == 0:
            keys.sort()                          # the plain-BST killer
        root = None
        for k in keys:
            root = avl_insert(root, k)
            assert check_bst(root)
            check_avl(root)
        assert list(in_order(root)) == sorted(keys)


def test_heap_pops_in_sorted_order():
    for trial in range(100):
        nums = [random.randint(0, 50) for _ in range(random.randint(0, 100))]
        h = MinHeap()
        for x in nums:                           # duplicates included, on purpose
            h.push(x)
            check_heap(h.items)
        out = []
        while len(h):
            out.append(h.pop())
            check_heap(h.items)
        assert out == sorted(nums)


def test_heap_matches_heapq():
    h, ref = MinHeap(), []
    for _ in range(5000):                     # random mix of pushes and pops
        if ref and random.random() < 0.4:
            assert h.pop() == heapq.heappop(ref)
        else:
            x = random.randint(0, 1000)
            h.push(x)
            heapq.heappush(ref, x)
    assert len(h) == len(ref)

Section 12Before next week