Heaps, Priority Queues, Dictionaries, and Hash Tables

Heaps, Priority Queues, Dictionaries, and Hash Tables

6.1 Heap Operations Recap

6.1.1 Insertion and the Bubble-Up Step

This session opens with a quick recap of last session: we ended with the heap data structure — a complete binary tree whose nodes are stored level by level in a vector, with the heap property holding at every node. Two things made the heap usable: its structural property (the tree stays complete, so the vector has no holes) and its relational property (a parent is ordered against its children — larger than them in a max heap, smaller in a min heap). We also saw how to insert an element into a heap and how to remove one from a heap. Both operations rely on one fixed procedure: heapification, which restores the heap property after the heap changes.

To insert a new element, push it into the first available leaf position of the heap, then bubble it upward until the heap property holds again. The first available leaf is simply the next free slot of the underlying vector — because the tree is complete, that slot is unique and easy to reach. So the placement step is a constant-time operation; the bubble-up does the real work. The new element keeps exchanging places with its parent while the heap property is violated, climbing one level per exchange.

This bubble-up cost is bounded by the height of the tree: in the worst case the new element is the smallest (in a min-heap) and must climb from a leaf all the way to the root. The professor's point during the recap was that these answers should come instantly — "there is nothing to think about if you have understood" — because the procedure and its cost are the same every time.

6.1.2 Removal and the Bubble-Down Step

Removal exchanges the root with the last leaf of the heap, removes the last element, then heapifies the remaining tree to restore the heap property. Note the discipline of this operation: we always remove the root element — that is the only element we remove from a heap; we never remove an arbitrary element. The root is the only node whose identity is guaranteed by the heap property (the maximum in a max heap, the minimum in a min heap), so it is the only node we can remove without first searching.

The steps in order: exchange the root with the last element, delete that last element, and bubble the new root downward (downheap). The old root now sits in the sorted-out portion of the story — in practice it is simply gone from the heap. The new root, which came up from the bottom, is probably too small (for a max heap), so it sinks, each time swapping with its larger child, until the heap property holds again. Like the bubble-up, this costs the height of the tree: the worst case is a value that must sink from the root all the way to a leaf.

6.1.3 Visual Intuition — The Two Bubbles

Picture the heap as a pyramid drawn inside a flat vector. The bubble-up is a vertical path that starts at a new leaf and rises: the path follows parent links, and at each level the new value swaps with its parent if needed. The bubble-down is the mirror image: a path that starts at the root and sinks, swapping with the larger child at each level. Both paths are single lines through the tree — never branches — and a single line through a binary tree of $n$ nodes is at most the height $h$ of the tree long. That is the whole reason both operations share the same cost: each does constant work at every level it touches, and the number of levels is $h$.

The landmark to notice is that both bubbles stop early in most cases: a new element that lands near its correct spot climbs only one or two levels, and a replacement root that is large enough sinks only one or two levels. The $O(h)$ bound is the worst case (a full vertical trip), not the common case. The one-sentence takeaway: insertion and removal are the same procedure facing opposite directions, and both are bounded by the height of the tree.

6.1.4 Student Questions and Answers

6.1.5 Exam Notes

Real-world connection: these two bubbles are the engine inside every heap consumer. Operating system schedulers keep ready processes in a priority heap and constantly insert new processes (upheap) and remove the highest-priority one (downheap); network routers do the same for packets waiting at a congested link. The same $O(\log n)$ pair of operations will power heapsort (Section 6.6) and Dijkstra's shortest-path algorithm later in the course, which repeatedly extracts the smallest remaining distance from a heap.

6.2 Fixing a Broken Heap

6.2.1 The Fix-Down Process

Consider a binary tree with left and right subtrees that are already heaps, but the root is not. What kind of heaps are the two subtrees? Max heaps — each is a valid max heap on its own. The whole tree is not a heap, only the subtrees are. How do we convert the whole tree into a heap? The tool is heapify, and we already met it last session: since this is a max heap, we compare the two children, find the maximum element among them, and exchange the root with that maximum; then we keep exchanging until the misplaced element finds its proper place.

Max-Heapify(A, i)
  l = 2i            // left child
  r = 2i + 1        // right child
  if l <= heap-size and A[l] > A[i]:  largest = l
  else:                                largest = i
  if r <= heap-size and A[r] > A[largest]:  largest = r
  if largest != i:
    exchange A[i] with A[largest]
    Max-Heapify(A, largest)

In the example shown during the session, the root holds 2 and its children hold 14 and 8. The larger child is 14, so 2 is exchanged with 14 — not with 8 — and the exchange repeats as 2 travels downward. One exchange at this level is not the end: 2 must keep descending until it lands at a leaf, so there is one more step beyond the first swap.

        2
       / \
      14  8
     / \ / \
    6  4 7  1

        14
       / \
      2   8
     / \ / \
    6  4 7  1

        14
       / \
      6   8
     / \ / \
    2  4 7  1

6.2.2 Assumptions and Scope

6.2.3 Visual Intuition — One Path, Downward

Picture the misplaced value as a stone dropped into a funnel of comparisons. At each level it faces exactly two candidates — its two children — picks the heavier one, and swaps places with it. The stone never goes up, and it never branches: it follows one straight line from its starting node down to a leaf. That line is the entire cost of heapify. The landmark is the end of the line: the stone stops either at a leaf or at a node where both children are smaller, and at that moment every parent on the path is larger than its children again. The one-sentence takeaway: heapify is a single downward path, and its time is the length of that path.

6.2.4 Common Pitfalls

6.2.5 Student Questions and Answers

6.2.6 Exam Notes

Real-world connection: heapify is the inner workhorse of every heap-based system — each extract-min in a priority queue and each round of heapsort runs a heapify. In network routing, Dijkstra's algorithm (later in the course) relies on exactly this operation: every time the shortest distance to a node is finalized, the distance heap must be repaired, and one heapify call per relaxation keeps the whole algorithm fast.

6.3 Constructing a Heap

6.3.1 The First Approach: Repeated Insertion

Given a heap, we know how to insert elements and how to remove the maximum. But how do we build a heap for a raw array of values? The most direct plan is repeated insertion: take the values one at a time and push them into an empty heap. Here is the naive analysis of that plan: each of the $n$ insertions triggers a heapification, and heapify costs $O(\log n)$, so the total cost of building the heap this way comes to $n\times O(\log n)=O(n\log n)$. That is the first, careless estimate — and it is the wrong one. The naive repeated-insertion construction costs $n$ times $O(\log n)$, which is $O(n\log n)$, but the professor stopped the class on this answer: the analysis is too loose, and a better look at the same process shows a much better bound.

6.3.2 A Full Walkthrough

Let's test that estimate with a concrete case. We insert eight elements — 13, 14, 15, 18, 11, 12, 17, 16 — one by one into a max heap, heapifying after each insert.

            18
       /          \
    16              17
   /  \            /  \
 15    11        12    14
 /
13

Counting the exchanges per inserted element shows that the naive analysis is loose: some inserts need no exchange at all, some need one, some need two, and none needed the full height of the tree. Yet the analysis charged every insert a full $O(\log n)$ heapify.

6.3.3 The Tighter View

The estimate above is loose because heapify at a node costs only as much as the height of that node, not the height of the whole tree. The heights of most nodes are small: out of $n$ nodes, about $n/2$ are leaves at height 0, about $n/4$ sit at height 1, and so on. Only a handful of nodes — the root and the level just below it — have large heights. So the analysis must charge each node only its own height, and then add up over the levels. That single change of perspective — charging each node its own height instead of the tree's height — is what the rest of this section develops.

6.3.4 A Second Walkthrough

The same eight elements can be read in a second way — as a raw initial array rather than a sequence of insertions. The processing starts with the last parent — the rightmost parent in the tree — and works leftward: the loop runs from $\lfloor n/2\rfloor$ down to 1.

Why start at the last parent? The leaf nodes are already heaps by themselves — a single node always satisfies the heap condition, since it has no children to violate it — so the last $n/2$ positions of the vector need no work at all. Processing starts at the node just before them, the rightmost parent at index $\lfloor n/2\rfloor$, and moves left until the root. If a subtree rooted at a node does not satisfy the heap condition, keep exchanging it with its largest child until the condition holds.

            18
       /          \
    16              17
   /  \            /  \
 14    11        12    15
 /
13

A second example makes the same point with ten values. The array is written into the tree shape with the values in the given order at locations 1 through 10 — 4, 1, 3, 2, 16, 9, 10, 14, 8, 7:

            4
       /          \
     1               3
   /   \           /   \
  2    16         9    10
 / \   /
14 8  7

The last five positions — 9, 10, 14, 8, 7 — are the leaf nodes, and they need no work at all. The instructor named exactly these values as the ones that are "already heaps", and the rightmost parent — the first node processed — is 16 at index $\lfloor 10/2\rfloor =5$, with the single child 7 below it. Processing from position 5 down to 1:

            16
       /          \
    14              10
   /   \           /   \
  8     7         9     3
 / \   /
2  4  1

6.3.5 The Algorithm in Full

In algorithmic form, the construction is called Build-Max-Heap. Initialize the structure with the keys in the given order — the array as it stands is already the heap-shaped tree, and all the exchange operations happen on the vector locations; there is no tree object anywhere. Then fix the heaps from the bottom up:

Build-Max-Heap(A)
  A.heap-size = A.length
  for i = floor(A.length / 2) down to 1:
    Max-Heapify(A, i)

Build-Max-Heap loops from $\lfloor n/2\rfloor$ — the floor of $n$ over 2 — down to 1, calling Max-Heapify at each index. Start with the last parental node and fix the heap rooted at it: if it does not satisfy the heap condition, keep exchanging it with its largest child until the condition holds — then move to the previous parent, and so on down to index 1. The leaf nodes are already heaps by themselves, so we never call heapify on them.

6.3.6 The Tight Analysis

The tighter analysis relies on two facts about an $n$-element heap: its height is $\lfloor {\log }_{2}n\rfloor$, and there are at most

$$\lceil \frac{n}{2^{h+1}}\rceil$$

— read "$n$ divided by 2 to the power $h$ plus 1" — nodes at any height $h$. At the leaves — height 0 — there are about $n/2$ nodes. Max-Heapify takes $O(1)$ time for the nodes one level above the leaves, $O(2)$ for the nodes two levels above, and $O(L)$ for the nodes $L$ levels above the leaves; at the root it takes $O(h)$, the height of the tree.

Summing these over the levels gives a linear total. At height $h$ there are at most $\lceil n/2^{h+1}\rceil$ nodes, and each costs $O(h)$:

$$\sum _{h=0}^{\lfloor {\log }_{2}n\rfloor }\lceil \frac{n}{2^{h+1}}\rceil \cdot O(h)=O\left(n\sum _{h=0}^{\lfloor {\log }_{2}n\rfloor }\frac{h}{2^h}\right)$$

The sum ${\sum }_{h=0}^{\infty }\frac{h}{2^h}$ is a standard series: writing $x=1/2$ in the identity ${\sum }_{h=0}^{\infty }h{x}^h=\frac{x}{(1-x{)}^2}$ gives $\frac{1/2}{(1/2{)}^2}=2$. So the total work is $O(2n)=O(n)$: building a heap takes linear time, $O(n)$, not $O(n\log n)$.

The reason the sum comes out linear, in the professor's words: the number of nodes where a height-2 repair is needed is smaller than the number where a height-1 repair is needed, and that trade-off — fewer nodes as the height grows — is what makes the sum come out linear. A separate reference document with the full mathematical proof is available for anyone who wants it; it is optional reading.

6.3.7 Assumptions and Scope

6.3.8 Common Pitfalls

6.3.9 Student Questions and Answers

6.3.10 Exam Notes

Real-world connection: the linear-time build matters wherever a priority queue must be created from a batch of data instead of being filled one element at a time — for example, when an event-driven simulator loads thousands of pending events at startup, or a router initializes its scheduling queues from a snapshot of waiting flows. Cutting the build from $O(n\log n)$ to $O(n)$ is exactly the kind of "day and night" difference the professor promised at scale.

6.4 The Priority Queue ADT

6.4.1 Definition and Main Methods

A priority queue is a container: every entry has an associated key, provided at the time the entry is inserted. The name comes from the fact that the keys determine which entries get removed, and in which order: the key of an entry is the priority of that entry. Each entry is a key–element pair — the key carries the priority, the element carries the data being served. The keys determine which entries get removed, and in which order: remove the entry whose key is smallest (a min-oriented priority queue) or largest (a max-oriented one).

The two main methods are insertItem$(k,o)$, which inserts an item with key $k$ and element $o$, and removeMin, which removes the item with the smallest key and returns its element. The remove-min operation removes the item with the smallest key and returns its element — nothing else in the queue is removed.

The remaining methods are standard: minKey returns the smallest key of an item but does not remove it; minElement returns the element of the item with the smallest key without removing it; size reports how many items the queue holds; isEmpty tells whether the queue is empty. All of these are implementation-based — you can implement them however you want — but these are the general, generic methods. minKey and minElement are the "look, don't touch" pair: they let an application peek at the next entry to be served without changing the queue.

6.4.2 Applications

Real-world: standby flyers. When airline seats are sold out and passengers sit on the waiting list, their priority is measured by the fare paid, the frequent-flyer status, or the check-in time, and the standby list behaves exactly like a priority queue: each waiting passenger is an entry, the priority factors are the key, and the passenger with the best combination is served first — not the one who joined the list first.

Real-world: sealed-bid auctions. Randomly arriving customers are privately informed about their own processing time and make bids upon arrival; a customer gets priority over all other customers waiting in the queue who made lower bids. The bid decides the order in which waiting customers are served — the higher the bid, the earlier the service.

Real-world: stock markets. When there are multiple possible buyers for a stock, the tie is broken by choosing the buyer that placed the bid earliest — or the lowest bid, depending on the model and the exchange's rules. Either way, the matching engine is a priority queue: buy and sell orders are entries, the price (and time of arrival) is the key, and the engine always matches the best-keyed orders first.

6.4.3 Total Order and Sorting with a Priority Queue

Like the heap, the priority queue requires a total order relation on keys — recall the three rules of total order studied just before heaps: every two keys are comparable (connected), the relation is transitive, and it is antisymmetric, so comparisons never disagree. Keys can be arbitrary objects on which an order is defined; two distinct items may carry the same key, and how equal keys are handled is a decision we make when we choose the implementation.

Sorting with a priority queue: given a collection of $n$ elements that can be compared according to the total order relation, insert them one by one with a series of insertItem operations, then remove them with a series of removeMin operations. This rearranges the collection in non-decreasing order. It is always safer to say non-decreasing rather than increasing, because multiple elements can have the same key; increasing order would forbid equal keys, while non-decreasing accommodates them.

6.4.4 Visual Intuition — A Line That Re-Sorts Itself

Picture a service desk with a single queue. Each customer carries a priority number, and the queue's rule is simple: whoever holds the smallest number is served next. When a new customer arrives, they do not stand at the back — the queue reorders so that the smallest number is always at the front, ready to be served. The two operations map cleanly onto this picture: insertItem is a customer joining the queue, removeMin is the customer at the front being served and leaving. minKey is the same as glancing at the front of the line without serving anyone. The landmark to watch is what happens with equal numbers: two customers with the same priority can stand anywhere relative to each other unless the implementation adds a rule (Section 6.5 shows the tie-break). The takeaway: a priority queue is a line whose order is decided by keys, not by arrival time.

6.4.5 Common Pitfalls

6.4.6 Student Questions and Answers

6.4.7 Exam Notes

Real-world connection: beyond the professor's standby-flyer, auction, and stock-exchange examples, priority queues run the schedulers inside operating systems (the ready queue of processes is keyed by priority), hospital emergency departments triage patients by severity, and network routers give delay-sensitive packets priority over bulk traffic — every one of these is the same key–element container, served by insertItem and removeMin.

6.5 Ways to Implement a Priority Queue

6.5.1 Sorted Sequence and Sorted Array

A sorted list or a sorted array is the obvious first idea: while inserting, you pay the cost of inserting at the correct position, and while removing, you remove from one end of the list. That trades cost for simplicity — and it makes the insertion step expensive. If we insert $n$ elements one by one into a sorted array, each insertion can cost $O(n)$ because all larger elements must shift, so we end up spending $O(n^2)$ total, and a sorted sequence is not a good starting point.

Why does insertion into a sorted array cost $O(n)$? The array is kept ordered at all times, so a new key must land between its smaller and larger neighbours. Finding the spot is fast, but making room is not: every larger element must shift one position to the right. If the new key is the smallest so far, every element shifts — the full $O(n)$ — and that happens over and over across $n$ insertions, for a total of $O(n^2)$. The removal side, by contrast, is trivial: the smallest item sits at one end, so removeMin just takes it — $O(1)$.

6.5.2 Unordered Sequence

An unordered sequence is the opposite: insertion is cheap — $O(1)$, we simply append — but finding the minimum requires a scan of the whole sequence, $O(n)$, and if we repeat that scan $n$ times we pay $O(n^2)$ again. Retrieval is what hurts. So both obvious sequence implementations are quadratic over a full workload; the difference is only where the pain lands. A sorted sequence pays on the way in (insert), an unordered sequence pays on the way out (find the minimum). Neither can be the foundation of a fast priority queue.

6.5.3 Heap-Based Implementation

A heap is the balanced choice. Keep a min-heap of key–element pairs — you need to keep track of the position of the last node so the next available location is always known. A heap-based priority queue gives $O(\log n)$ for both insert and remove-min. With a sorted array, that same insertion would have cost $O(n)$ — that is exactly why we do not use a plain array for a priority queue.

       2
      / \
     5   6
    / \
   9   7

       2
      / \
     5   3
    / \ / \
   9  7 6

6.5.4 Comparison and Choice

Comparison of the three implementations:

With an unordered sequence, insert is $O(1)$ and removeMin is $O(n)$; with a sorted sequence, insert is $O(n)$ and removeMin is $O(1)$, because the smallest item sits at the first (or last) location; with a heap, both operations are $O(\log n)$. The heap gives a balanced, average performance of $O(\log n)$ everywhere, while the sequence implementations are each excellent at one operation and poor at the other.

No implementation wins everywhere, so you have to choose between the two based on the application: if your application needs more inserts, choose the heap; if it needs more extractions, choose the sorted sequence. Make a balanced decision — when $n$ is large, $n$ and $\log n$ make a difference of day and night; they are not anywhere close. The professor's closing line on this comparison: don't think $n$ and $\log n$ are somewhere close — for very large $n$ the difference is like day and night, so you must choose the implementation by the application's operation mix.

6.5.5 Assumptions and Scope

6.5.6 Student Questions and Answers

6.5.7 Exam Notes

Real-world connection: real priority queues live inside operating-system schedulers and network routers, where the workload is a mix of inserts and extractions, so the heap is the default choice; a sorted sequence shows up where removals dominate — for example, a list of deadlines that only ever removes the earliest one, like expiry timers that fire in order.

6.6 Heapsort

6.6.1 The Algorithm

Heapsort turns the heap into a sorting method. Heapsort sorts an unsorted array $A$: the output is the same array modified to be sorted from smallest to largest. The input is the array $A[1\dots n]$ in any order; the output is the very same array, now in non-decreasing order — no second array is created.

Why does this sort? The heap property guarantees that the root is the largest remaining element. Each round takes that largest element and parks it at the end of the current heap region — which is exactly its final position in the sorted array. The heapify call then promotes the next largest to the root, ready for the next round. After $n-1$ rounds every element has been moved into the sorted tail, and the array is fully sorted.

6.6.2 A Worked Example

Start from a heap already built — building it took $O(n)$ time, the linear-time algorithm we studied. The heap is the ten-element max heap 16, 14, 10, 8, 7, 9, 3, 2, 4, 1, so the roots run 16, 14, 10 across the first rounds.

6.6.3 Time and Space

Time: building the heap costs $O(n)$; the loop runs $n-1$ times and each Max-Heapify costs $O(\log n)$, so the total is

$$O(n)+(n-1)\cdot O(\log n)=O(n)+O(n\log n)=O(n\log n)$$

Heapsort totals $O(n)$ for the build plus $O(n\log n)$ for the loop, giving $O(n\log n)$. The linear build step cannot rescue the total: although building the heap is linear, removing the maximum one by one forces $n$ heapifications, and that part cannot be helped. The runtime of the whole algorithm is $O(n\log n)$ — a summary the professor delivered with a mock plea not to ask why again: the build is linear, the removal loop is not, and the loop dominates.

Space: the swap-with-the-last-element trick keeps everything in one array — the sorted portion grows at the back of the same array — so the sort can be done in place. Building the heap is also done in place, using the same array. If instead you insist on maintaining a separate sorted list, you would need one more array of the same size.

6.6.4 Visual Intuition — The Array with Two Regions

Picture the array as a single strip with a moving boundary. Everything to the left of the boundary is the heap — a pyramid standing on its vector base, with the current maximum at its peak. Everything to the right of the boundary is the sorted tail — flat, finished, in ascending order. Each round does three things: the peak of the pyramid is lifted off and laid down just to the right of the boundary; the boundary shifts one position left; and the pyramid is re-carved (heapify) so a new peak appears. The landmark is the boundary itself: after round $k$, the last $k$ positions hold the $k$ largest elements in sorted order, and the heap region is exactly $n-k$ elements tall. The takeaway: one array hosting two structures — a shrinking heap and a growing sorted tail — with no second array anywhere.

6.6.5 Common Pitfalls

6.6.6 Student Questions and Answers

6.6.7 Exam Notes

Real-world connection: heapsort's guarantee of $O(n\log n)$ in every case — no bad inputs, no extra memory — makes it the choice for systems where memory is precious and worst-case behaviour matters, such as embedded controllers and real-time systems. The same extract-max loop also answers selection-style questions (the first $k$ largest elements of a stream) by stopping early, which is why priority-queue machinery appears inside analytics systems that rank incoming records.

6.7 The Helper Operations of a Heap

6.7.1 Navigation within the Vector

Given a vector-based heap and an index $i$, the three navigation rules are constant-time operations. The parent of the node is at $\lfloor i/2\rfloor$ — the floor of $i$ divided by 2, written in the standard form the reference text uses; the left child is at $2i$; the right child is at $2i+1$ — "two $i$ plus one". These are all $O(1)$ operations — simple index arithmetic on the vector, with no tree traversal.

The tree picture is only a way of seeing the vector; the vector locations are the reality. The three rules are exactly what make the heap work without pointers: instead of following a link from one node to another, we multiply or divide the index, and the arithmetic lands on the neighbouring node. In algorithmic form:

Parent(i):  return floor(i / 2)
Left(i):    return 2i
Right(i):   return 2i + 1

Note the direction of these rules: a node's parent index is roughly half its own index, and its children are about double — so a path from a leaf to the root shrinks the index by half at every step, which is why any climb or descent through the heap touches at most $O(\log n)$ nodes.

6.7.2 Heap Increase Key

Heap increase key handles the case where the value at a node goes up. Given an array $A$ representing a heap, an index $i$, and a new key greater than $A[i]$, we keep exchanging the node with its parent while the parent is smaller, until the node finds its place — an upward bubble, exactly like upheap. The cost is $O(\log n)$ because it is a heapification process.

Why does raising a value only need an upward bubble? Raising a key can only violate the heap property in one direction: a parent is required to be at least as large as its children, so a node that just got bigger can only be too big for its own parent — its children are untouched, since the value only grew. Walking upward, exchanging with any smaller parent, restores the property along the whole path.

            18
       /          \
    16              17
   /  \            /  \
 15    11        12    14
 /
13

Real-world: the price of an item in an auction can be increased; the value of a stock can be increased; the priority of a customer suddenly increases because they decide to pay more. In each case the stored key rises, and increase key restores the heap.

6.7.3 Extract Max and Insert

Extract max: in a max heap the root holds the maximum element — that is the catch, and it is why extraction is a $O(\log n)$ operation: take the root, and heapify. Every one of these methods is the heapification process in another disguise, so every one runs in $O(\log n)$:

• Extract max — remove the root (the maximum), then Max-Heapify: $O(\log n)$.
• Max heap insert — the insertion procedure from before: place the new element at the next available location and bubble upward: $O(\log n)$.
• Increase key — raise a stored key and bubble upward: $O(\log n)$.

And a final reminder from the session: Build-Max-Heap can be done in either $O(n\log n)$ or linear time — always do the linear version.

6.7.4 Assumptions and Scope

6.7.5 Student Questions and Answers

6.7.6 Exam Notes

Real-world connection: increase key is the operation behind priority upgrades in live systems — a network packet that receives a "pay more" tag in a metered queue, a job whose urgency is raised by an operator, or a Dijkstra-style shortest-path engine (later in the course) where a tentative distance that improves must be promoted inside the heap. In each case the data structure must react to a rising key in logarithmic time, not a full rebuild.

6.8 Binary Search and the Case for Dictionaries

6.8.1 Binary Search on a Sorted List

Given a sorted list of numbers, what is the best search algorithm? Binary search: it works by divide and conquer — it halves the candidate range at every step — and runs in $O(\log n)$. That is the standard answer, and it is still far from $O(1)$. If you could find an algorithm that searches an element in $O(1)$ time from a list of $n$ elements, with $n$ large, you would be the king — you would rule the world. That remark connects to the complexity classes NP-hard and NP-complete, which come up near the end of the course: an $O(1)$-or-even-sublinear search for arbitrary data would be the kind of breakthrough that reshapes what we think is computable.

6.8.2 Why a Dictionary

Binary search is good, so why do we study dictionaries? Because we want an algorithm that does better than binary search. With a dictionary, the search for an element is $O(1)$ — but understand that this is the expected time, the average time. Nobody states it explicitly, but it is an average; sometimes the search enters $O(n)$ itself, with a dictionary too. On average $O(1)$, worst case worse — that is the honest summary we build toward. The professor's garbled aside about "alpha" points exactly where the refinement lives: next session the expected-time analysis will be stated precisely in terms of the load factor, the ratio of stored items to table cells, and that is where the "on average" qualifier gets its real shape. For now, the claim stands in its honest form: expected $O(1)$, worst case worse.

6.8.3 Visual Intuition — The Halving Search

Picture a sorted list as a long measuring tape with the target value hidden somewhere along it. At every step of binary search you look at the middle mark: if the tape's value there is smaller than the target, the target must lie in the right half, so you tear off the left half and discard it; if larger, you discard the right half. Each step halves the remaining tape, so the number of steps is the number of times you can halve $n$ before one mark is left — ${\log }_{2}n$. The landmark is the middle mark itself: it is the only point of the tape you ever need to inspect. The takeaway: binary search trades sorted order for a guarantee that every comparison discards half the possibilities — excellent, but each search still has to be told where to look one element at a time, which is the gap a dictionary attacks.

6.8.4 Student Questions and Answers

6.8.5 Exam Notes

Real-world connection: the professor closed the search discussion by pointing at Google's PageRank — the search-ranking algorithm by Larry Page, published as a paper by Google's founders. PageRank is a graph-based algorithm: it ranks web pages by the structure of links between them rather than by scanning lists, which is why the professor placed it "in alignment with the graph data structure we will be studying very soon". Dictionaries, meanwhile, are the everyday engine of lookups in compilers (symbol tables), operating systems (environment registries), and every language's built-in map.

6.9 The Dictionary ADT

6.9.1 Definition and Main Operations

A dictionary stores key–element pairs, which we call items. $K$ is the key and $E$ is the element. The dictionary models a searchable collection of items: the main operations are inserting, searching, and deleting. An item is stored with its key, and a search looks up the element by key. A key is an identifier that is assigned by an application or a user to an associated element — in a dictionary of student records, for instance, the key might be the student's ID number and the element the student's full record. The benefit we are chasing: insert, search, and delete in $O(1)$ time — but whether it is exactly $O(1)$ or something more is what the coming sections decide. To be precise from the start: findElement is $O(1)$ on average but can reach $O(n)$ in the worst case.

The methods: findElement$(k)$ returns the element of the item with key $k$; if the dictionary has no item with that key, it returns a special element called noSuchKey — a sentinel, a marker value that signals "not found" and can never be confused with a real element. insertItem$(k,e)$ inserts an item with element $e$ and key $k$. removeElement$(k)$ removes the item with key $k$. Then the generic methods size and isEmpty, and the iterator methods keys() and elements() — keys() walks through all the keys of the dictionary, elements() through all the elements. Because duplicate keys are allowed (next subsection), the dictionary can also offer findAllElements$(k)$, which returns an iterator over all elements whose key equals $k$, and removeAllElements$(k)$, which removes them all at once.

6.9.2 Duplicate Items and Collisions

Is it possible to store two entries with one key in a dictionary? The instinctive answer is no — a key should be unique. But the answer is yes: it is allowed. When multiple entries share the same key, you get a collision, and we will study how to handle — not eliminate — the collision: a collision is a collision; once it happens we can handle it, and we can reduce future ones, with strategies we will see with hash tables. Collisions are the price of duplicate keys, and choosing a good key is the first line of defense.

6.9.3 Choosing a Good Key

The lesson of the duplicates discussion: choose keys with as few duplicates as possible. A bad key choice — hashing the category "fruits" to values like apple, banana, orange — guarantees collisions; do not choose a key like that. The same holds for first names: many people share a first name — Bob Smith and Bob John produce the identical hash value — so a first name is a poor key. For student records, the natural key is the student's ID number, and we would probably want to disallow two students sharing one ID number. Choose the key smartly, so that it has as few duplicates as possible.

6.9.4 Examples

Real-world: the classic dictionary example maps countries to their currency — the currency of Greece is euro. Dictionaries use an array-like syntax for indexing: dictionary[Greece] returns euro. Unlike a standard array, the indices of a dictionary need not be consecutive, and they need not even be numeric — here the keys are strings, the country names. That is the whole point of the array-like syntax: the "index" is whatever key the application chose, and the lookup returns the element attached to that key.

Real-world: counting the number of occurrences of words in a document — the word counting example — a dictionary is ideal: use the words as keys and the word counts as values.

6.9.5 Assumptions and Scope

6.9.6 Common Pitfalls

6.9.7 Student Questions and Answers

6.9.8 Exam Notes

Real-world connection: dictionaries are the lookup engine of nearly every program — the compiler's symbol table maps identifiers to types and addresses, the operating system maps environment variable names to their values, and every web application maps user IDs to session data. The professor's country-to-currency and word-counting examples are miniature versions of these; the word-counting one is directly implementable with Python's dictionary class, which is itself a real, tuned hash-table dictionary.

6.10 The Log File Implementation

6.10.1 Definition and Costs

A log file is a dictionary implemented with an unsorted sequence: the items of the dictionary are stored in the sequence in arbitrary order — whichever order they happened to arrive in. This is also called the unordered-sequence implementation of the dictionary ADT, and its three costs are easy to derive.

The space required is $O(n)$ — the structure keeps its memory usage proportional to its size. Insertion takes $O(1)$, because there is no order to maintain; we simply append. findElement and removeElement for a key $k$ take $O(n)$, because the sequence must be scanned: to find an item with a given key we walk the sequence from the start, comparing keys one by one, until the key is found or the sequence ends.

6.10.2 When a Log File Makes Sense

Real-world: a log file is exactly what companies use for login records. If you are logging the punch-in and punch-out details of employees — login records with timestamps — you seldom search them: only when there is a dispute, when an employee claims a login time different from the one registered, does anyone search the log file. The file is searched rarely — searches and removals are very rare in such a file — so the $O(n)$ scan, paid once in a while, is perfectly manageable.

As each employee punches in, the details are inserted one after another, with no ordering by employee name or employee number. The log grows by appending: employee 5 punches in at 9:02, employee 12 at 9:04, employee 5 again at 9:05 — each record lands at the end, in arrival order. There is no index, no sort, no structure to maintain, and that is precisely why insertion stays $O(1)$.

The log file is effective only for small dictionaries, or for dictionaries on which insertions are the most common operations — whenever searches, deletions, or accesses dominate, we need a better implementation, and that is where the hash table enters.

6.10.3 Visual Intuition — The Append-Only Ledger

Picture a paper ledger with one line per event, written in chronological order — an audit trail. Every punch-in is a new line at the bottom; nobody reorders the lines and nobody deletes them. Finding a particular employee's record means reading the ledger from the top until the matching line appears — the whole book, in the worst case. The landmark is the bottom of the ledger: that is where every new record lands, in constant time, which is why the ledger is so cheap to keep. The takeaway: a log file is a dictionary that optimizes the write side and accepts an expensive read side, because its real-world workloads read rarely.

6.10.4 Assumptions and Scope

6.10.5 Student Questions and Answers

6.10.6 Exam Notes

Real-world connection: the log-file pattern is everywhere in industry under the name append-only log or audit trail: system event logs, database write-ahead logs, and version-control histories all share the same shape — write constantly, read rarely, and when a read happens, scan or replay. The professor's login-records example is the same pattern in miniature: companies keep the punch-in and punch-out details precisely because they are cheap to write, and the search cost is paid only in disputes.

6.11 Bucket Arrays and Hashing

6.11.1 Bucket Array and Hash Function

A dictionary that must answer searches fast is built with hashing. The data structure: a bucket array of size $n$, together with a hash function $h$. The goal: for a key–element pair $(k,e)$, the bucket array stores the pair at location $h(k)$ — not at $k$, not at $e$, at the location the hash function computes from the key. The array is called the bucket array because each location is a bucket: in the ideal case every bucket holds exactly one item; when a bucket must hold several, that is where collisions begin. Together, the bucket array and the hash function form the hash table — the structure a dictionary implementation is built on.

A bucket array needs keys that are unique integers in the range $0$ to $n-1$ — and that requirement has two built-in challenges. First, the keys we actually have may not be integers at all. Second, even integer keys may span a range far larger than the table — keys in the range $0$ to some huge number, with only 100 locations available. The hash function solves both: it converts any key to an integer, and it brings that integer into the range $0$ to $n-1$.

6.11.2 Hash Values with Integer Keys

For integer keys, the simplest hash function is the modulo function: $h(x)=x\mathrm{mod}n$. The value $h(x)$ is called the hash value of the key $x$. Example: with $h(k)=k\mathrm{mod}6$, the key 10 hashes to 4. Keys with hash value 6 all land in location 6 — and that is the beginning of collisions: for whichever element the hash value is 6, all those elements are stored in the same bucket. If keys are not unique, two different elements may be mapped to the same bucket, and that is when we say a collision has occurred.

A hash function is good if it maps the keys of our dictionary so as to minimize the collisions as much as possible. If a key is not an integer, other methods apply: for a string you can use the number of letters, the ASCII characters of the string, or a polynomial conversion; the standard polynomial method multiplies each ASCII character by a positional factor. These are standard conversion techniques worth exploring on your own.

6.11.3 Two Jobs of a Hash Function

A hash function has two jobs, with two names. Hash code mapping: convert the key — whatever its type — into an integer. Second, compression mapping: bring that integer into the range $0$ to $n-1$, usually by taking it modulo $n$. The order matters: hash code mapping is applied first, and then compression mapping. Compression mapping is needed even when the keys are already integers, if they lie in a larger range than the table size.

For a dictionary storing social security numbers (nine-digit positive integers) with names, a simple hash function is the last four digits of the number: $h(x)=x\mathrm{mod}10000$. The social security number 000000001 hashes to 1, so it is stored at location 1. The modular form and the "last four digits" rule agree exactly: the remainder after dividing by 10000 is the number's last four digits, so an SSN ending in 0001 always lands at location 1. Python's built-in hash function shows the same two-stage idea — try it out: for a string it applies the polynomial mapping to the characters.

6.11.4 Visual Intuition — The Funnel and the Boxes

Picture a row of boxes labeled 0 through $n-1$ — the bucket array. Above them hangs a funnel with a dial: the hash function. Every key is dropped into the funnel, the dial spins, and the key falls into the box whose label the dial printed. A good hash function spreads the falling keys across all the boxes; a bad one dumps many keys into the same box. The landmark to watch is a box holding more than one key — a collision — because that is the moment handling machinery is needed. The takeaway: hashing turns "find where this key lives" into "compute one number and walk to that box" — the whole speed of the dictionary rests on that single computation.

6.11.5 Common Pitfalls

6.11.6 Student Questions and Answers

6.11.7 Exam Notes

Real-world connection: every serious language runtime is a hash-table shop — Python's dictionary and hash() built-in, Java's HashMap, and C++'s unordered_map all apply hash code mapping (Python uses the polynomial mapping for strings) and then a compression step into the table's range. Compiler symbol tables and environment-variable registries are the same structure: names as keys, properties as elements, and a hash function deciding where each name lives.

6.12 Table Size and Prime Numbers

6.12.1 Why the Size Should Be Prime

The size $n$ of the hash table is usually chosen to be a prime number — any real-world implementation you will see does this. The full reason is a number-theory proof, beyond the scope of the course, but the intuition is simple, because the bias is easy to see. Suppose the table size is even, and the keys we insert are also even. Then every computed index $k\mathrm{mod}n$ is even: the table develops a bias — only the even locations fill, only half of the slots are used, and the odd indices never get used at all. The reverse holds too: an odd size can leave the even indices unused, depending on the keys.

The modular arithmetic behind it: an even size $n$ and an even key $k$ always give an even remainder, because an even number minus any multiple of an even number is still even. So with $n$ even, half the table — all odd locations — can never be reached by even keys. A prime size spreads the indices evenly, so collisions drop. If you want the full mathematical argument, it is a long proof that you can look up — the professor's advice was to skip it unless you are a maths expert, because the conceptual reason is the part that matters.

6.12.2 A Worked Example with an Even Size

Worked example: after hash code mapping, suppose the keys are 200, 205, 210, 215, 220, and so on, in steps of 5, up to 600 — and the bucket size is 100, an even number.

6.12.3 Visual Intuition — The Half-Empty Table

Picture a bar chart of the 100 buckets of the example, with bucket index 0 to 99 on the horizontal axis and the number of stored items on the vertical axis. The filled bars stand only over the multiples of 5 — 0, 5, 10, ..., 95 — each four or five units tall; the other 80 positions are empty ground. The landmark is the empty stretch: an entire half of the table that even keys can never reach. With $n=101$, the same 81 keys produce 81 separate single-item bars with no empty pattern at all. The takeaway: a non-prime size lets the keys' own structure repeat inside the table, and repetition is what turns into collisions.

6.12.4 Common Pitfalls

6.12.5 Student Questions and Answers

Real-world connection: real hash tables nearly always size their tables at prime numbers — Java's HashMap uses prime table sizes (with power-of-two sizes chosen only after randomized hash spreading), and Python grows its dictionaries through a sequence of prime-capacity sizes. The same modulo-bias reasoning also explains why databases and caches pick prime-sized hash buckets when the data keys are known to follow patterns such as multiples or arithmetic progressions.

6.13 Handling Collisions

6.13.1 Why Collisions Happen

Collisions occur when different elements are mapped to the same cell. Can collisions be avoided? Not really. However good the hash function, we cannot predict the incoming keys — the keys that will arrive tomorrow, or the day after tomorrow — so sooner or later two keys land in one cell. Collisions are unavoidable, and the effort spent hunting for a perfect hash function is not worth it compared with handling them: most real-world systems simply handle collisions. The best hash function in the world is useless against keys you cannot foresee. So the question is not "how do we prevent collisions" but "what do we do when one happens" — and the very first method, the subject of the rest of this section, is very direct: separate chaining.

6.13.2 Separate Chaining

The first collision handling method is very direct: separate chaining. Let each cell in the table point to a linked list of the elements that map there. Each bucket holds that linked list: the array location stores a pointer to the head of the list, and every item whose key hashes to that cell is appended to it. Instead of one array, we have a bucket array where each location is the head of its own list. In the ideal case — a good hash function, few collisions — most buckets are empty or hold a single item, and the lists are tiny. When a bucket must hold several, the list simply grows: the hash table itself never gets filled up, because wherever a collision occurs, the linked list grows.

6.13.3 Algorithms

The algorithms are straightforward, and each delegates the work to the list sitting in the bucket. Let $B=A[h(k)]$ — the list stored at the bucket for key $k$.

• findElement$(k)$: if $B$ is empty, return the sentinel noSuchKey; otherwise search for the key $k$ inside the sequence $B$, walking the linked list from the head, and return the element found.
• insertItem$(k,e)$: if $A[h(k)]$ is empty, create a new, initially empty, sequence-based dictionary — the linked list — and attach it to the bucket; otherwise take the existing list; then insert the item with key $k$ and element $e$ into that list.
• removeElement$(k)$: get the list at $A[h(k)]$; if it is empty, return noSuchKey; otherwise remove the item with the key.

Separate chaining sets $B$ equal to the list at $A[h(k)]$ and searches it; in the worst case — a bucket whose list holds many items — findElement takes $O(n)$. The hash function's spreading power is what keeps the lists short: with a good function most buckets hold zero or one item, and each operation stays near constant time.

6.13.4 A Worked Example

6.13.5 Pros and Cons

Separate chaining is simple, direct, and easy to implement — that is its great strength. It also never fills up: the hash table itself never becomes full, because wherever a collision occurs, the linked list simply grows. The weakness is space and access speed. If too many elements map to one location, the list at that bucket grows toward $n$ items, and searching an $n$-sized linked list costs $O(n)$ — read "big-O of n" — at that point the advantage of the dictionary is gone, and the whole bucket-array-and-lists machinery is worse than just using a plain array or a plain linked list. If many collisions occur, every advantage for which the dictionary was chosen is invalidated, and the time complexity climbs.

6.13.6 Visual Intuition — Chains Hanging from Buckets

Picture the bucket array as a row of hooks, labeled 0 through $n-1$, with chains hanging from some of them. A key arrives, the hash function points at a hook, and the item is clipped onto the chain there — behind any items already hanging. Most hooks hold nothing or one item; the chain hangs from a hook only where collisions have happened. The landmark is the longest chain: its length is the worst case for any search, because finding an item at that bucket means walking the whole chain. The takeaway: separate chaining converts "table full" into "chains grow", and the price of that flexibility is paid wherever a chain grows long.

6.13.7 Common Pitfalls

6.13.8 Student Questions and Answers

6.13.9 Exam Notes

Real-world connection: separate chaining is the collision strategy inside some of the most-used hash tables in industry — Java's HashMap chains its buckets, and DNS caches and database hash indexes grow chains when keys collide. The professor's design rule transfers directly: real systems accept collisions as a fact of life, spend their effort on handling them, and rely on the hash function plus a good table size (prime, as in Section 6.12) to keep the chains short.

Exam Guidance Summary

• Mid-sem syllabus: everything studied so far, plus binary search tree and dictionary — the syllabus ends at binary search tree. The dictionary topic is completed in the next session; binary search tree starts Monday, with an extra session announced in advance (Monday 7 to 9 PM).
• Sample paper: it will be discussed in Monday's session, not uploaded — if the pattern did not match exactly, there would be complaints.
• Dictionary: half covered in this session (definition, log file, hash tables, separate chaining); the rest, including the two remaining collision handling methods, comes in the next session.
• Building a heap: the answer is $O(n)$, linear time, with the loop from $n/2$ down to 1. The mathematical proof of the $O(n)$ bound is not asked in the exam — with a search engine the proof would simply be copied out.
• Heapify: expect conceptual questions like "why is 14 exchanged and not 8" — the max-heap rule: compare the children, take the maximum, and exchange with that one.
• Priority queue sorting: always phrase the output as non-decreasing order, to accommodate equal keys.
• Heapsort: practice question of the session — "after you construct this heap, show what happens when you increase the key 5 from 5 to 33, then do heapsort and explain why the runtime of this algorithm is $O(n\log n)$". Heapsort returns in the sorting unit later in the course — "keep this in mind".
• Recall questions (insertion steps, removal steps, upheap and downheap complexities) should be answered instantly — there is nothing to think about if you have understood.
• Dictionary search: the $O(1)$ claim is an average, expected-time claim; the worst case is $O(n)$ — say this carefully in answers, and never "close your eyes and say $O(1)$".
• The $n$ versus $n\log n$ difference matters at large scale: make the balanced implementation choice with that in mind — when $n$ is large, $n$ and $\log n$ make a difference of day and night.

Key Industry Applications

• Priority queues: standby flyers (priority by fare paid, frequent-flyer status, or check-in time); sealed-bid auctions (customers bid on arrival and gain priority over lower bids); stock markets (matching buyers and sellers, tie-breaking by earliest bid or lowest bid — the matching engine is a priority queue either way).
• Heap increase key: auction item prices rising, stock values rising, a customer's priority rising because they decide to pay more — in each case the stored key rises and the heap is repaired in logarithmic time.
• Log files: punch-in and punch-out login records in companies — insertion-heavy, search-rare (only disputes are searched), so the $O(n)$ scan is paid once in a while. The same append-only pattern drives system event logs and audit trails.
• Dictionaries: counting word occurrences in a document — words as keys, counts as values; implement directly with the Python dictionary class. Compiler symbol tables and environment-variable registries are dictionaries in disguise.
• Hash tables: Python's built-in hash function shows hash code mapping (polynomial mapping for strings) followed by compression; social security number tables use the last-four-digits hash $h(x)=x\mathrm{mod}10000$. Real runtimes — Python, Java, C++ — all implement the dictionary on top of hash tables with prime-sized growth.
• Google PageRank: the search ranking algorithm by Larry Page — a graph-based algorithm, aligned with the graph data structure topic that comes next (graphs begin in a few sessions).
• General principle: if the application needs many inserts, choose the heap; if it needs many extractions, choose the sorted sequence — when $n$ is large, $n$ and $\log n$ differ by day and night.