An algorithm is only as good as the data structure it works on. We have already caught glimpses of this in the previous lessons: a dict turned Rutalia's duplicate detector from quadratic to linear, and a table made dynamic programming viable. In this lesson we systematize that knowledge: we will briefly review the basic structures and then study in depth four structures that multiply a developer's reach: the heap (priority queue), the hash table, union-find, and the trie. For each one: how it works, what its operations cost, when to use it, and how Rutalia uses it.

1. Quick review: array, linked list, stack, and queue
2. Heaps and priority queues (heapq)
3. Hash tables: dict and set
4. Union-Find (disjoint sets)
5. Tries (prefix trees)
6. A selection guide

These four structures are assumed known; the table pins down vocabulary and costs, which we will use as a reference:

Two practical warnings:

• Do not use list as a FIFO queue: pop(0) shifts every element, O(n) per operation. collections.deque does popleft() in O(1).
• The call stack from lesson 01-03 is, quite literally, a stack: a LIFO of function frames.

These structures answer "give me the last one", "give me the first one", or "give me the i-th one" well. The four that follow answer richer questions: "give me the most urgent one", "does this id exist?", "are these two zones connected?", "which addresses start with...?".

Orders arrive at the operations center continuously, each with a priority (its delivery deadline). Dispatchers need, over and over again, the most urgent pending order. With a list: either you search for the minimum every time (O(n) per extraction) or you keep the list sorted (O(n) per insertion). With a million operations a day, both options are quadratic in total.

A binary min-heap is a complete binary tree (all levels full except possibly the last one, which fills from left to right) satisfying the heap property: every node is ≤ its children. Consequences:

• The minimum is always at the root: peeking at it is O(1).
• The tree is balanced by construction: its height is ⌊log₂ n⌋.
• Insertion: place the element at the end and let it "float up" while it is smaller than its parent → O(log n).
• Extracting the minimum: remove the root, move the last element up to the root, and let it "sink down" by swapping with the smaller of its children → O(log n).

And the implementation trick that makes it so efficient: being complete, it is stored in a plain array with no pointers. Node i has its children at 2i+1 and 2i+2, and its parent at (i−1)//2.

The heapq module operates on a plain list, treating it as a min-heap. For composite priorities you use tuples (compared element by element):

Important details:

• heapq is always a min-heap. For a max-heap, insert negated keys (-priority).
• If two tuples tie on the first field, the second is compared; including an incrementing counter as a tiebreaker avoids errors when comparing non-comparable objects: (priority, counter, order).
• Processing n orders with push+pop costs O(n log n) in total, versus the O(n²) of the list-based solutions.

When to use it: whenever you repeatedly need "the best/smallest/most urgent" element of a dynamically changing set. A connection we will cash in during module 3: Dijkstra's shortest-path algorithm (lesson 03-03) is, in essence, a loop over a priority queue; without a heap it would be impractical at city scale.

Customer support gets: "where is my order P-58201?". With the list of orders, every query is an O(n) linear search. With thousands of queries a day over a million orders, unacceptable.

A hash table stores key→value pairs in an array of m slots (buckets). A hash function turns each key into an index: index = hash(key) % m. Ideally, finding a key means computing its hash and going straight to the bucket: O(1) regardless of n.

The unavoidable problem: two keys can land in the same bucket (a collision). Conceptually, the two families of solutions:

• Chaining: each bucket holds a small list of the pairs that land in it; searching means scanning that list.
• Open addressing: if the bucket is occupied, another one is tried following a probing sequence (this is what CPython does for dict).

As long as the load factor (n/m) stays low and the hash function spreads keys well, the chains/probes are short and operations cost O(1) on average. When the table gets too full, it is resized (rehashed) — a one-off O(n) cost which, like the append of lesson 01-02, comes out to O(1) amortized. The theoretical worst case (all keys colliding) is O(n), but with Python's hash functions it is irrelevant in ordinary practice.

dict (key→value) and set (keys only) are native hash tables:

Requirement: keys must be hashable (immutable): numbers, strings, tuples of immutables. Lists and dicts cannot be keys — which is why in lesson 01-03 we memoized with (r, c) tuples.

When to use it: membership, indexing by key, deduplication, counting (collections.Counter). It is the structure that already rescued the duplicate detector in 01-02. When not to: if you need key order or ranges ("orders between 10:00 and 11:00"), the hash table does not help; that is where sorted data and binary search come in (lesson 04-01).

The city is divided into delivery zones. Some streets between zones get closed off (roadworks, street markets); the system receives events "zone A and zone B are now connected by an open crossing" and queries "can I get from zone X to zone Y using only open crossings?". We need to group elements into components that keep merging, and quickly ask whether two elements belong to the same group.

Union-Find (or disjoint set union, DSU) maintains a collection of disjoint sets with two operations:

• find(x): returns the representative of x's set (two elements are in the same set if and only if they have the same representative).
• union(x, y): merges the sets of x and y.

Implementation: each element points to a "parent"; the representative is the root of that pointer tree. Naively the trees can degenerate into chains (find O(n)); two classic optimizations prevent it:

• Union by rank: when merging, the root of the shorter tree is hung from the root of the taller one, keeping the trees shallow.
• Path compression: each find re-attaches every node it visits directly to the root, flattening the tree for the future.

With both, the amortized cost per operation is O(α(n)), where α is the inverse of the Ackermann function: it grows so slowly that α(n) ≤ 4 for any physically possible n. In practice: constant.

Line by line, the essentials:

• find is recursive: it climbs up to the root and, on the way back, rewrites each parent[x] to point directly at it. The next query on any of those nodes will be a single hop.
• union returns False if the elements were already connected — an extremely useful detail for detecting cycles.

Limitation: union-find only merges; it does not support "closing a crossing" (un-merging) efficiently. If connections can also be destroyed, other techniques are needed.

When to use it: incremental connectivity, clustering, cycle detection. Another forward connection: Kruskal's minimum spanning tree algorithm (lesson 03-04) consists of scanning edges in sorted order while asking a union-find whether each edge connects distinct components.

The couriers' app autocompletes addresses: the user types "ma" and "Main Street", "Maple Street", "Market Square"… must appear. Searching the full list with startswith costs O(n·L) per keystroke (n addresses of average length L). We need a structure that organizes strings by their prefixes.

A trie is a tree where each edge carries a character; each node represents the prefix formed by the path from the root, and terminal nodes mark complete words. All words sharing a prefix share that prefix's path.

Costs, with L = length of the queried string (they do not depend on the number n of words!):

How the code works:

• Each node is simply a dict of children: we are leveraging the hash table from section 3 as a building block (composing structures — a common pattern).
• insert walks down creating nodes as needed: exactly L steps.
• with_prefix has two phases: walking down the prefix (O(L)) and traversing the subtree while accumulating words. For autocompletion, in practice you cap the number of results returned.

When to use it: autocompletion, spell checkers, hierarchical paths, prefix search in general. When not to: if you only need exact lookup, a set is simpler and more compact; the trie only earns its extra memory when prefixes matter.

The question each structure answers, in one decision table:

In Rutalia's system they all live side by side: a dict indexes orders by id, a heap orders dispatch by urgency, a union-find answers questions about connected zones, and a trie autocompletes the street directory. Choosing a structure means translating your system's most frequent question into the right row of this table.

• Using list as a FIFO queue or as a set. pop(0) is O(n) and x in some_list is O(n). These are probably the two most common performance mistakes in Python: deque and set fix them at the root.
• Searching inside a heap. A heap only guarantees where the minimum is; locating or updating an arbitrary element is O(n). The standard pattern for "changing a priority" is to insert the new entry and discard the stale one when it is extracted (marking it as obsolete).
• Putting non-comparable objects into heapq. If two tuples tie on the priority, Python compares the next field; if it is a dict, exception. Solution: a (priority, counter, item) tuple with an incrementing counter.
• Using mutable keys in dict/set. Lists are not hashable (immediate error); and even if a custom object is hashable, mutating it after insertion corrupts its location in the table. Immutable keys, always.
• Relying on a dict's order as key order. Python dicts preserve insertion order, not key order. For ranges or sorting, you have to sort separately.
• Implementing union-find without the two optimizations. Without compression and rank, the trees degenerate and every find can be O(n); over large sequences of unions the difference is hours versus seconds. They are five lines: always include them.
• Choosing a trie for exact lookup. If you never ask about prefixes, the trie only brings memory consumption and complexity. The simplest structure that answers your dominant question is the right one.
• Tip: before writing code, phrase your system's most frequent operation in one sentence ("I need X millions of times a day...") and find its row in the section 6 table. That minute of reflection prevents most rewrites.

Implement dispatch(orders, k) which takes a list of (deadline, id) tuples and returns the k most urgent orders in order, using heapq. State the complexity of your solution and compare it with sorting the full list. Which one is better if n = 1,000,000 and k = 10?

Rutalia has n zones (0..n−1) and a list of open crossings crossings = [(a, b), ...]. Write components(n, crossings) returning how many groups of mutually reachable zones there are, using the lesson's UnionFind class. Example: components(6, [(0,1), (1,2), (4,5)]) → 3 (groups {0,1,2}, {3}, {4,5}).

Extend the Trie class with a method count_prefix(prefix) returning how many addresses start with the prefix, in O(L) — without traversing the subtree. Hint: store in each node a counter that is incremented on insertion.

Solution 1

Complexity: O(n + k·log n). Sorting the full list is O(n log n). With n = 10⁶ and k = 10: ~10⁶ + 10·20 operations versus ~2·10⁷; the heap wins clearly because it does not pay to sort what is never dispatched. (Even more direct: heapq.nsmallest(k, orders) does essentially this.) If k ≈ n, both options converge to O(n log n) and sorting is simpler.

Solution 2

Cost: O(n + m·α(n)) for m crossings — practically linear. The trick of counting via union's return value avoids a final pass looking for distinct roots. Common mistake: counting every call to union as a merge without checking whether the elements were already connected.

Solution 3

Each node records how many words pass through that prefix; count_prefix only walks down L levels → O(L), independent of the number of addresses. (With this variant, the "#" and END keys coexist with the child characters; the traversal in with_prefix must skip both. If duplicate words are inserted, the counter counts them all — decide whether that is what you want.)

We close the first module with the toolbox complete. The basic structures (array, linked list, stack, queue) answer positional questions; the advanced ones answer higher-value questions: the heap delivers the highest-priority element in O(log n) and is the engine behind heapq's priority queues; the hash table (dict/set) gives membership and indexing in O(1) average in exchange for giving up ordering; union-find with path compression and union by rank maintains merging groups in practically constant time; and the trie organizes strings by prefixes, making autocompletion independent of the size of the street directory. At Rutalia, each one solves a concrete business question: prioritizing urgent orders, locating an order instantly, knowing whether two zones are still connected, and suggesting addresses as you type. And we have planted two seeds: the heap is the piece that will make Dijkstra efficient (lesson 03-03) and union-find will do the same for Kruskal (lesson 03-04).

This wraps up the introduction: we know how to express costs (01-01), calculate them (01-02), design with recursion and dynamic programming (01-03), and lean on the right structures (01-04). In module 2, Optimization Algorithms, we move from analyzing to deciding: Rutalia will no longer ask "how much does this operation cost?" but "what is the best possible allocation of resources?" — starting with linear programming (02-01) and continuing with combinatorial optimization, backtracking and branch and bound, genetic algorithms, and ant colonies.