Module 2 in One Sitting

Priority queues and heaps

A priority queue serves the most urgent item, not the earliest. The ADT is insert, remove_best, peek_best.

A binary heap is a complete binary tree with the heap order property: in a min-heap every parent is less than or equal to its children. Complete means it fills level by level, left to right, which is why it fits in an array with no pointers: for index i the children are 2i+1 and 2i+2 and the parent is (i-1)/2.

Sift up restores order after an insertion at the end; sift down restores it after the top is removed and the last element is moved there. Both are O(log n) because the tree's height is.

Building a heap from n items is O(n), not O(n log n), because most nodes are near the bottom and sift down from a low node is cheap. This is a standard question and the reason is the marks.

A heap gives O(1) peek at the best, O(log n) insert and O(log n) removal of the best, and O(n) to find anything else, because only the top is ordered relative to everything.

Graphs

A graph is vertices joined by edges, with no restriction: cycles and multiple paths are allowed, which is exactly what a tree forbids. Directed or undirected, weighted or unweighted.

The vocabulary that earns marks: degree, in-degree and out-degree, path, simple path, cycle, connected, complete, sparse and dense. The sum of all degrees is twice the number of edges. A complete undirected graph has n(n-1)/2 edges.

Two representations. An adjacency matrix is V by V, gives O(1) edge lookup, and costs V squared memory whatever the graph; at 10,000 vertices and 20,000 edges it is 99.96 per cent zeros. An adjacency list keeps a list of neighbours per vertex, costs V + 2E, and gives O(degree) neighbour access. A full traversal is exactly V squared probes on a matrix and exactly 2E on a list, which is why every algorithm is written against a list.

BFS uses a queue and visits in order of increasing distance, so a vertex's level is its shortest distance in edges. DFS uses a stack, usually the recursion stack, and goes deep before wide; a DFS depth is not a distance. Both are O(V + E) on a list and O(V squared) on a matrix. The visited set is what makes either one terminate, not an optimisation.

Connectivity. One traversal from any vertex reaching all V means connected. Starting a fresh traversal from each unvisited vertex finds every component, still in O(V + E) in total. An isolated vertex is a component. A connected graph needs at least V-1 edges; exactly V-1 and connected means a tree.

Shortest paths. Unweighted: BFS already solves it, and reaching for Dijkstra is the commonest over-answer. Weighted and non-negative: Dijkstra, settling the nearest unsettled vertex and relaxing its edges, O((V + E) log V) with a heap or O(V squared) with an array scan. A negative edge breaks it, because settling means final: the chapter's example settled a vertex at 1 when the truth was 0 and reported no error. Bellman-Ford handles negative weights.

Hashing

Hashing computes a record's address from its key instead of searching for it, so a lookup does not depend on how much is stored. The hash function maps any key into 0 to m-1; the array is the hash table and a slot is a bucket.

Four methods. Division, h(k) = k mod m, fastest, and m must be a prime, never a power of 10 or 2. Mid-square, the middle digits of k squared, because they depend on every digit of the key. Folding, the sum of the key's pieces, for long keys. Multiplication, floor(m x fractional part of k x A) with A about 0.6180339887, which works for any m.

A good hash function is uniform over the actual keys, deterministic, cheap, uses the whole key, and sends similar keys to unrelated slots. It is good or bad only relative to a key set.

Collisions are certain, not unlucky. Pigeonhole: more keys than buckets forces one. Birthday: a collision becomes more likely than not at about 1.25 times the square root of m, so a table of a million buckets starts colliding at about a thousand records, 0.1 per cent full.

Three strategies. Chaining gives each bucket a list: alpha may exceed 1, deletion is a plain unlink, costs are alpha for a miss and 1 + alpha/2 for a hit. Linear probing puts everything in the array: no pointers, best cache behaviour, but primary clustering, and a cleared slot breaks the probe chain, so deletion needs a tombstone. Quadratic probing removes primary clustering but reaches only (m+1)/2 slots with m prime, so m must be prime and alpha below 0.5. Double hashing makes the step depend on the key and has no clustering of either kind.

The load factor alpha = n/m decides everything. Chaining's cost grows linearly in it; every open addressing cost blows up as it approaches 1. So the table is rehashed at a threshold: a larger table, the next prime at least double, and every record hashed again, because the slot was k mod m and m has changed. Doubling makes this amortised O(1); growing by a fixed amount makes the total O(n squared).

What hashing gives up is every question about order: minimum, maximum, range, successor, sorted output and rank all cost O(m + n), which means examining everything. That is the sentence that separates a good answer from a list.

The six "advantages and disadvantages", in one line each

Binary search tree. Ordered and simple; degenerates to O(n) on sorted input.

AVL tree. The only guaranteed O(log n) here, and ordered; rotations on every insertion and deletion, and deletion may rotate to the root.

Heap. O(1) at the best item and O(n) to build; nothing but the top is reachable in less than O(n).

Adjacency matrix. O(1) edge lookup and a trivially simple structure; V squared memory always, and every traversal becomes O(V squared).

Adjacency list. Memory proportional to the edges and O(V + E) traversal; edge lookup is O(degree).

Hash table. O(1) average for insert, search and delete, with no ordering needed on the keys; no ordered query at all, an O(n) worst case, deliberately empty space, and total dependence on the hash function.

What Module 2 cannot do

No structure here answers a prefix query. A trie does; a hash table cannot and a tree needs the keys ordered by that prefix.

No structure here gives O(1) worst case search. Hashing is O(1) average, AVL is O(log n) guaranteed, and the comparison lower bound of chapter 99 says no comparison based method can beat log2(n).

No structure here gives both O(1) exact lookup and O(log n) range queries. Two structures together do, at the price of duplicated keys, which chapter 110 prices.

The five mark answers most likely to be asked

The three BST deletion cases, with a worked example of the two-child case replacing by the inorder successor.

The four AVL rotations, with the insertion that triggers each one and the resulting tree.

Why building a heap is O(n), with the argument about most nodes being near the bottom.

Adjacency matrix against adjacency list, with the memory figures and the O(V + E) against O(V squared) traversal.

BFS and DFS, both algorithms, their complexities, and which solves the unweighted shortest path and why.

Dijkstra's algorithm traced on a small weighted graph, including the relax step changing a vertex's distance, and why a negative edge breaks it.

Collision handling, with chaining and linear probing both built, the load factor formulas, and the tombstone.

Hash functions, any two methods with the arithmetic shown, and why m should be prime.

Test yourself

1. What single property distinguishes a graph from a tree? A tree has no cycle and exactly one path between any two vertices. A graph allows cycles and multiple paths, so a tree is a connected acyclic graph.

2. Which traversal of a binary search tree gives sorted order, and which pair rebuilds a tree? Inorder gives sorted order. Rebuilding needs two traversals of which one is inorder: inorder with preorder, or inorder with postorder.

3. Why does a binary heap need no pointers? Because it is a complete binary tree, which fills level by level left to right, so the nodes map onto array positions with children at 2i+1 and 2i+2 and the parent at (i-1)/2.

4. State the cost of a full graph traversal on each representation and explain the difference. Exactly V squared probes on a matrix, because every row is scanned in full, and exactly 2E on a list, because only real edges are read. So BFS and DFS are O(V squared) and O(V + E) respectively.

5. Why is BFS, not Dijkstra, the answer for an unweighted shortest path? Because with equal weights cheapest means fewest edges, which BFS already gives by its level numbers, at O(V + E) against Dijkstra's O((V + E) log V).

6. Why does a negative edge break Dijkstra's algorithm? Because settling the nearest unsettled vertex is justified only by no edge being able to reduce a total. With a negative edge a settled vertex may still be improvable, and a settled vertex is never revisited.

7. Why are collisions certain rather than unlucky? Give both arguments. Pigeonhole: more keys than buckets forces a shared bucket, whatever the hash function. Birthday: a collision is more likely than not at about 1.25 times the square root of m, so a million bucket table collides at about a thousand records.

8. What goes wrong if a deleted slot in a linear probing table is simply cleared? The probe chain is broken, so records placed beyond the cleared slot become unreachable: a search stops at the now empty slot and reports absent although the record is in the table. A tombstone is required.

9. Give the load factor formulas for chaining. Unsuccessful search alpha, successful search 1 + alpha/2, and insertion one probe without a duplicate check.

10. What is the single most important thing hashing gives up? Every question about order. The minimum, maximum, a range, the successor, sorted output and the k-th smallest each cost O(m + n), which is examining the whole table, so they are not slow operations but operations the structure cannot perform.