Unit 5: Heaps and Hashing

Part 1: Heaps

1. Introduction to Heaps

A Heap is a specialized tree-based data structure that satisfies the heap property. It is essentially an almost complete binary tree. Heaps are primarily used to implement Priority Queues and the HeapSort algorithm.

There are two main types of heaps:

1. Max-Heap: For any given node , the value of is greater than or equal to the values of its children. The largest element is at the root.
2. Min-Heap: For any given node , the value of is less than or equal to the values of its children. The smallest element is at the root.

Array Representation:
Because a heap is a complete binary tree, it can be efficiently represented using an array without pointers.
For a node at index (0-based index):

• Parent:
• Left Child:
• Right Child:

2. Insertion in a Heap

Inserting a new element involves maintaining the complete binary tree structure and restoring the heap property (Heapify Up).

Algorithm (Max-Heap):

1. Add the new element to the end of the array (the first available leaf position).
2. Compare the new element with its parent.
3. If the new element is greater than the parent, swap them.
4. Repeat step 2-3 until the element reaches the root or is smaller than its parent.

Time Complexity: (where is the number of nodes).

3. Deletion in a Heap

Deletion usually refers to removing the root element (the maximum in a Max-Heap or minimum in a Min-Heap), as this is the primary operation of a priority queue.

Algorithm (Delete Max from Max-Heap):

1. Remove the root element (index 0).
2. Replace the root with the last element in the heap (the last leaf).
3. Decrease the heap size by 1.
4. Heapify Down (Percolate Down):
   • Compare the new root with its children.
   • If the root is smaller than the largest child, swap it with that child.
   • Repeat until the node is a leaf or larger than both children.

Time Complexity: .

4. HeapSort

HeapSort is a comparison-based sorting algorithm that uses a Binary Heap data structure. It sorts an array in two phases.

Phase 1: Build Heap
Convert the unsorted array into a Max-Heap. This is done by calling heapify on all non-leaf nodes starting from the last non-leaf node up to the root.

• Time complexity to build heap: .

Phase 2: Extraction
Repeatedly extract the maximum element from the heap to build the sorted array.

1. Swap the root (maximum value) with the last element of the heap.
2. Reduce the heap size by 1 (effectively "sorting" the max element at the end of the array).
3. Call heapify on the new root to restore the Max-Heap property.
4. Repeat until the heap size is 1.

Complexity Analysis:

• Time Complexity: for Best, Average, and Worst cases.
• Space Complexity: (In-place sort).
• Stability: Not Stable.

Part 2: Hashing Introduction

1. Basic Concepts

Hashing is a technique used to convert a range of key values into a range of indexes of an array. It allows for the efficient storage and retrieval of data.

• Goal: To perform Insertion, Deletion, and Search operations in time on average.
• Hash Table: An array of size where data is stored.
• Hash Function: A mathematical function that maps a key to an index in the range .
• Collision: Occurs when two distinct keys map to the same index, i.e., where .

2. Hash Functions

A good hash function should:

1. Be easy to compute.
2. Distribute keys uniformly across the hash table to minimize collisions.

Common Methods:

• Division Method: . (Best if is a prime number).
• Multiplication Method: , where .
• Mid-Square Method: Square the key and extract the middle digits.
• Folding Method: Divide the key into parts and add them together.

Part 3: Open Hashing (Separate Chaining)

Open Hashing, also known as Separate Chaining, is a collision resolution technique where the hash table is an array of pointers (or references) to linked lists.

Mechanism

1. The hash function calculates the index: .
2. If the slot at Table[i] is empty, a new linked list is initiated, and the key is inserted.
3. If Table[i] is occupied (collision), the new key is appended to the linked list at that index.

Operations

• Insert: Compute hash, insert at the head (or tail) of the linked list.
• Search: Compute hash, traverse the linked list at that index.
• Delete: Compute hash, search the list, and remove the node.

Pros and Cons

• Pros:
  • Simple to implement.
  • The hash table never fills up (we can always add nodes to the lists).
  • Less sensitive to the hash function's quality or load factor.
• Cons:
  • Requires extra memory for linked list pointers.
  • Cache performance is poor due to non-contiguous memory allocation (linked lists).

Part 4: Closed Hashing (Open Addressing)

In Closed Hashing (Open Addressing), all elements are stored directly within the hash table array. No external data structures (like linked lists) are used.

If a collision occurs, the algorithm searches for the next available empty slot using a probing sequence.

• Load Factor (): Number of elements / Table Size. In open addressing, must be .

1. Linear Probing

If a collision occurs at index , check the next index sequentially.

Formula:

• Process: Check , then , then , wrapping around if necessary until an empty slot is found.
• Issue - Primary Clustering: Continuous blocks of occupied cells form. Any key hashing into the cluster extends the cluster, increasing search time for future insertions.

2. Quadratic Probing

Instead of a constant step size (1), the step size increases quadratically to reduce primary clustering.

Formula:

• Process: Check , then , then , then , etc.
• Issue - Secondary Clustering: Keys hashing to the same initial position follow the exact same probe sequence.
• Constraint: Table size should ideally be a prime number congruent to to ensure the probe hits at least half the table.

3. Double Hashing

Uses a second hash function to determine the step size if a collision occurs. This is the most efficient open addressing method.

Formula:

• : Primary hash function.
• : Secondary hash function (must never yield 0).
• : Probe number .

Properties of :

1. It must be different from .
2. Values must be relatively prime to the table size to ensure the probe sequence visits all slots.
   • Common choice: If is prime, , where is a prime.

Advantage: Eliminates both primary and secondary clustering (uniform hashing).

Summary Comparison