Unit 5: Heaps and Hashing

I. Foundations — Ordered Trees and Direct-Access Storage

Heaps and hashing provide efficient ways to organize and retrieve data. A heap maintains a partial order that supports priority-based operations, while hashing transforms keys into array indices to support near-constant-time search, insertion, and deletion.

• Heap principle: A complete binary tree obeys either the max-heap or min-heap order property.
• Hashing principle: A hash function maps a key (k) to a table index.
• Primary goals:
  • Heaps efficiently identify and remove the highest- or lowest-priority element.
  • Hash tables efficiently locate records by key.
• Core difficulty:
  • Heap updates may disturb heap order and require restructuring.
  • Different keys may hash to the same index, causing a collision.
• Complexity convention: (n) denotes the number of stored elements, and (m) denotes the number of hash-table slots.

II. Heaps — Priority-Ordered Complete Binary Trees

A heap is a complete binary tree whose nodes satisfy a consistent parent-child ordering. It is commonly stored in an array, avoiding explicit pointers while preserving tree relationships.

A. Introduction to heaps

A heap combines a structural property with an ordering property to provide efficient access to an extreme element.

• Complete binary tree: Every level is full except possibly the last, which is filled from left to right.
• Max-heap property: Every parent is greater than or equal to its children, so the maximum element is at the root.
• Min-heap property: Every parent is less than or equal to its children, so the minimum element is at the root.
• Partial order: Siblings and nodes in separate subtrees need not be ordered relative to one another.
• Array representation: For zero-based index (i):
  • Parent: (\lfloor(i-1)/2\rfloor)
  • Left child: (2i+1)
  • Right child: (2i+2)
• Height: A heap containing (n) nodes has height (\lfloor\log_2 n\rfloor).
• Extreme-element access: Reading the root takes (O(1)) time.
• Common use: Priority queues use heaps to process elements according to priority rather than arrival order.

B. Heap insertion

Heap insertion places a new element at the next available leaf and then restores heap order upward.

• Structural step: Append the value to the array, preserving the complete-tree property.
• Up-heap operation: Compare the inserted node with its parent and swap them while the heap property is violated.
• Max-heap condition: Swap while heap[parent] < heap[i].
• Min-heap condition: Swap while heap[parent] > heap[i].
• Pseudocode:

INSERT_MAX(heap, value):
    append value to heap
    i = heap.size - 1
    while i > 0:
        p = floor((i - 1) / 2)
        if heap[p] >= heap[i]:
            break
        swap heap[p], heap[i]
        i = p

Here, (i) is the current index and (p) is its parent index.

• Worked example: Insert (45) into max-heap [50, 30, 40, 10, 20, 35].
  • Append (45): [50, 30, 40, 10, 20, 35, 45].
  • Compare (45) with parent (40), then swap.
  • Result: [50, 30, 45, 10, 20, 35, 40].
• Complexity: At most one root-to-leaf height is traversed, so insertion is (O(\log n)).

C. Heap deletion

Heap deletion normally removes the root, replaces it with the final element, and restores order downward.

• Root removal: Save the root because it is the maximum in a max-heap or minimum in a min-heap.
• Structural repair: Move the last array element to index (0), then reduce the heap size.
• Down-heap operation: Swap the replacement with the appropriate child until heap order is restored.
• Child selection:
  • A max-heap chooses the larger child.
  • A min-heap chooses the smaller child.
• Pseudocode:

DELETE_MAX(heap):
    maximum = heap[0]
    heap[0] = heap[last]
    remove last element
    i = 0
    while i has a child:
        c = index of larger child
        if heap[i] >= heap[c]:
            break
        swap heap[i], heap[c]
        i = c
    return maximum

Here, (i) is the node being repaired and (c) is its selected child.

• Worked example: Delete from [50, 30, 45, 10, 20, 35, 40].
  • Replace (50) with (40): [40, 30, 45, 10, 20, 35].
  • Swap (40) with larger child (45).
  • Result: [45, 30, 40, 10, 20, 35].
• Complexity: Root deletion takes (O(\log n)); reading the root without deletion takes (O(1)).

D. Heap sort

Heap sort uses a heap to repeatedly place the largest remaining element into its final sorted position.

• Build phase: Convert the array into a max-heap by applying down-heap from the last internal node to the root.
• Selection phase: Swap the root with the final element in the active heap.
• Reduction phase: Decrease the active heap size and restore max-heap order at the root.
• Pseudocode:

HEAP_SORT(A):
    BUILD_MAX_HEAP(A)
    for end = A.length - 1 down to 1:
        swap A[0], A[end]
        MAX_HEAPIFY(A, 0, end)

Here, (A) is the array and end is the exclusive boundary of the reduced heap after the swap.

• Complexity: Building the heap is (O(n)); repeated removals require (O(n\log n)) total time.
• Space: An array-based implementation is in-place and uses (O(1)) auxiliary space.
• Characteristics: Heap sort is comparison-based and not stable because distant swaps can reverse equal elements.

E. Applications and limitations

Heaps are most useful when repeated access to an extreme-priority element matters more than complete ordering.

• Applications: Priority queues, CPU scheduling, event simulation, graph algorithms such as Dijkstra’s algorithm, and selection of the (k) largest or smallest values.
• Strength: Insert and extreme deletion both take (O(\log n)).
• Limitation: Searching for an arbitrary value remains (O(n)) because heap order is only partial.
• Limitation: A binary search tree is generally more suitable when ordered traversal or range queries are required.

III. Hashing — Key-to-Index Mapping

Hashing stores records according to computed positions rather than comparisons. Its performance depends on a well-designed hash function, an appropriate table size, and an effective collision-resolution method.

A. Introduction to hashing

Hashing converts a key into a table location so that records can usually be accessed directly.

• Key: The identifying value, such as a student number or username.
• Hash value: The integer index produced from the key.
• Collision: A collision occurs when distinct keys (k_1) and (k_2) satisfy (h(k_1)=h(k_2)).
• Expected performance: Search, insertion, and deletion average (O(1)) with controlled collisions.
• Worst case: If many keys collide, an operation may degrade to (O(n)).
• Load factor:

α = n / m

Here, (\alpha) is the load factor, (n) is the number of stored keys, and (m) is the number of slots.

B. Hash functions

A hash function deterministically maps each key to a valid table index and should distribute likely keys uniformly.

• Range requirement: For a table of size (m), (h(k)) must lie from (0) to (m-1).
• Division method:

h(k) = k mod m

Here, (k) is an integer key and (m) is the table size; a prime (m) often reduces patterns in the keys.

• String hashing: Character codes can be accumulated polynomially:

h = (h × b + code(character)) mod m

Here, (b) is a fixed base and (m) bounds the result.

• Quality criteria: A function should be fast, deterministic, influenced by the whole key, and resistant to clustering.
• Worked example: With (m=11), (h(47)=47\bmod11=3), so key (47) initially maps to slot (3).

C. Hash tables

A hash table is an array whose entries hold records directly or refer to collections of colliding records.

• Insertion: Compute (h(k)), then store the record using the table’s collision policy.
• Search: Follow the same mapping and collision sequence used during insertion.
• Deletion: Remove the record without breaking access to other colliding records.
• Load management: When (\alpha) becomes too high, the table can be resized and all keys rehashed.
• Rehashing: Rehashing allocates a larger table and recomputes every key’s position because indices depend on (m).
• Ordering limitation: Hash tables do not naturally support sorted traversal, predecessor queries, or efficient key ranges.

IV. Hash-Collision Resolution — Chaining and Probing

Collision resolution determines where a key is stored when its initial hash location is occupied. The two broad strategies are open hashing and closed hashing.

A. Open hashing

Open hashing allows multiple keys to belong to the same table index by storing them outside the primary array slots.

• Bucket principle: Each index identifies a bucket containing all keys with that hash value.
• Load factor: (\alpha) may exceed (1) because one bucket can contain several records.
• Search path: Compute the bucket index, then inspect only that bucket.
• Expected cost: With uniform hashing, operations are approximately (O(1+\alpha)).
• Trade-off: Collision handling is simple, but nodes or dynamic containers require additional memory.

B. Separate chaining

Separate chaining implements open hashing by associating each table index with a chain of records.

• Representation: A bucket may use a linked list, dynamic array, or balanced tree.
• Insertion: Compute (h(k)) and add the record to that bucket, often at the list head in (O(1)).
• Search: Compute (h(k)), then compare keys within the selected chain.
• Deletion: Remove the matching chain node; no special marker is required.
• Worked example: If (m=5) and (h(k)=k\bmod5), keys (12), (22), and (7) all occupy the chain at index (2).
• Limitation: Poor distribution creates long chains and can reduce operations to (O(n)).

C. Closed hashing

Closed hashing stores every record inside the fixed table array and searches for another slot after a collision.

• Storage rule: Each slot holds at most one record, so normally (0\leq\alpha<1).
• Probe sequence: A deterministic sequence examines candidate slots until the key or an available position is found.
• Memory locality: Array-only storage usually has better cache behavior than linked chains.
• Capacity restriction: Insertion fails when no usable slot remains unless the table is resized.
• Performance effect: As (\alpha) approaches (1), probe sequences become longer.

D. Open addressing

Open addressing is the standard implementation of closed hashing, with collisions resolved by probing alternative array positions.

• General formula:

h(k, i) = probe position for key k after i collisions

Here, (k) is the key and (i=0,1,\ldots,m-1) is the probe number.

• Search rule: Follow the exact insertion sequence until the key is found or a never-used slot is reached.
• Deletion rule: Mark a removed slot as DELETED; making it immediately empty could incorrectly terminate later searches.
• Insertion rule: A DELETED slot may be reused, while duplicate-key handling follows the table’s record policy.
• Requirement: A probe sequence should be capable of reaching enough, ideally all, table positions.

E. Linear probing

Linear probing checks consecutive table positions after a collision.

• Formula:

h(k, i) = (h'(k) + i) mod m

Here, (h'(k)) is the initial hash, (i) is the probe number, and (m) is the table size.

• Worked example: If (m=10), (h'(27)=7), and slots (7) and (8) are occupied, probes occur at (7,8,9); key (27) enters slot (9).
• Strength: The method is simple and cache-friendly because nearby locations are examined.
• Primary clustering: Long runs of occupied slots form, attracting more colliding keys and increasing probe lengths.
• Practical condition: Performance is usually maintained by resizing before the table becomes heavily loaded.

F. Quadratic probing

Quadratic probing uses a nonlinear offset to reduce the primary clustering caused by consecutive probes.

• Formula:

h(k, i) = (h'(k) + c1i + c2i²) mod m

Here, (c_1) and (c_2) are constants, (i) is the probe number, and (m) is the table size.

• Probe pattern: With (c_1=0) and (c_2=1), offsets are (0,1,4,9,\ldots).
• Strength: Keys disperse more widely than with linear probing, reducing primary clustering.
• Secondary clustering: Keys with the same initial hash still follow the same probe sequence.
• Constraint: Suitable choices of (m), (c_1), and (c_2), together with a moderate load factor, are needed to ensure insertion finds a free slot.

G. Double hashing

Double hashing uses a second hash function as the probe step, producing key-dependent probe sequences.

• Formula:

h(k, i) = (h1(k) + i × h2(k)) mod m

Here, (h_1(k)) gives the initial index, (h_2(k)) gives the step size, and (i) counts probes.

• Step requirement: (h_2(k)) must never be zero and should be relatively prime to (m), allowing all slots to be visited.
• Typical construction:

h1(k) = k mod m
h2(k) = R - (k mod R)

Here, (R) is a prime smaller than (m).

• Strength: Different keys usually follow different probe sequences, reducing both primary and secondary clustering.
• Trade-off: Two hash computations make it slightly more expensive than linear or quadratic probing, but collision behavior is generally better.