Min Heap

Definition and Properties

Definition

Min heap: complete binary tree with key at root ≤ keys of children. Guarantees minimum element access in O(1) time. Used for priority queues, graph algorithms.

Heap Property

For every node i except root: key(parent(i)) ≤ key(i). Ensures global minimum at root, local min-heap order holds.

Completeness

Tree is complete: all levels fully filled except possibly last, filled left to right. Enables array representation.

Uniqueness

Heap not necessarily unique for given set of keys. Structure depends on insertion order and heapify.

Structure and Representation

Binary Tree Structure

Min heap is binary tree: each node has ≤ 2 children. Balanced due to completeness property.

Array Representation

Stored in array A[1..n]. Parent(i) = floor(i/2), Left Child(i) = 2i, Right Child(i) = 2i + 1.

Index Calculations

Efficient navigation using indices, no explicit pointers needed, reduces memory overhead.

Memory Layout

Contiguous memory improves cache locality, speeds up traversal and operations.

Example

Example array: [2, 4, 5, 7, 10, 6] represents min heap with 2 at root.

Basic Operations

Find Minimum

Return root element. Time complexity: O(1).

Insertion

Add element at end, then "bubble up" to restore heap property.

Deletion of Minimum

Remove root, replace with last element, then "bubble down" to restore heap property.

Heapify

Convert arbitrary array into min heap in O(n) time by bottom-up adjustment.

Insertion Algorithm

Step-by-Step Process

Insert element at end (next free leaf). Compare with parent; if smaller, swap. Repeat until heap property restored or root reached.

Bubble Up (Percolate Up)

Ensures new key moves upward to correct position; maintains structure and ordering.

Complexity

Worst-case time: O(log n), height of heap.

Pseudocode

function insert(heap, key): heap.size += 1 i = heap.size heap[i] = key while i > 1 and heap[parent(i)] > heap[i]: swap(heap[i], heap[parent(i)]) i = parent(i)

Deletion Algorithm

Deleting Minimum

Remove root (minimum). Replace root with last element. Reduce heap size by one.

Bubble Down (Percolate Down)

Compare replaced root with children. Swap with smaller child if heap property violated. Repeat until restored.

Complexity

Worst-case time: O(log n), proportional to heap height.

Pseudocode

function deleteMin(heap): if heap.size == 0: return error min = heap[1] heap[1] = heap[heap.size] heap.size -= 1 heapifyDown(heap, 1) return minfunction heapifyDown(heap, i): left = 2 * i right = 2 * i + 1 smallest = i if left <= heap.size and heap[left] < heap[smallest]: smallest = left if right <= heap.size and heap[right] < heap[smallest]: smallest = right if smallest != i: swap(heap[i], heap[smallest]) heapifyDown(heap, smallest)

Heapify Process

Purpose

Transform arbitrary array into valid min heap.

Bottom-Up Approach

Start from last non-leaf node, apply heapifyDown repeatedly upward to root.

Time Complexity

O(n), more efficient than repeated insertions.

Algorithm Steps

function buildMinHeap(array): n = length(array) for i = floor(n/2) down to 1: heapifyDown(array, i)

Explanation

Leaves are trivially heaps. Heapify propagates heap property upwards.

Time Complexity Analysis

Insertion

O(log n): at most moves up height of heap.

Deletion of Minimum

O(log n): bubble down along height.

Find Minimum

O(1): root element directly accessible.

Building Heap

O(n): bottom-up heapify more efficient than n insertions (O(n log n)).

Summary Table

Applications of Min Heap

Priority Queues

Efficient minimum extraction and insertion. Used in scheduling, resource management.

Dijkstra’s Algorithm

Min heap stores vertices with shortest tentative distances. Speeds up shortest path computation.

Huffman Coding

Builds optimal prefix codes by repeatedly merging nodes with smallest frequencies.

Heap Sort

Min heap variant used to sort data in ascending order.

Median Finding

Combined with max heap to maintain dynamic median in streaming data.

Comparison with Max Heap

Heap Property

Min heap: parent ≤ children; max heap: parent ≥ children.

Root Element

Min heap root minimum; max heap root maximum.

Use Cases

Min heap: minimum extraction priority; max heap: maximum extraction priority.

Operations

Insertion, deletion algorithms structurally identical, differ only in comparison direction.

Implementation Details

Data Structures

Typically array-based for space and time efficiency. Can use pointers in tree form for educational purposes.

Memory Considerations

Array size fixed or dynamic; resizing policies affect amortized costs.

Language Support

Most languages support arrays; heap usually implemented as class or struct with size attribute.

Code Example (Insertion)

class MinHeap: def __init__(self): self.heap = [] def insert(self, key): self.heap.append(key) i = len(self.heap) - 1 while i > 0 and self.heap[(i-1)//2] > self.heap[i]: self.heap[i], self.heap[(i-1)//2] = self.heap[(i-1)//2], self.heap[i] i = (i-1)//2

Advantages and Limitations

Advantages

Fast minimum extraction (O(1)), efficient insert/delete (O(log n)), simple implementation, good cache performance.

Limitations

Not efficient for arbitrary element search (O(n)), no direct support for decrease-key unless augmented, fixed branching factor limits flexibility.

Alternatives

Fibonacci heaps: better amortized decrease-key; Binomial heaps: better for merging heaps.

Advanced Topics

Decrease-Key Operation

Critical in graph algorithms. Min heap requires index tracking or auxiliary data structures.

Merge Heaps

Binary min heap inefficient for merging. Other heap types better suited.

d-ary Heaps

Generalization with d children per node. Tradeoff between height and percolation cost.

Implicit Data Structures

Array-based heaps avoid pointers. Used in memory-constrained environments.

Parallel Heaps

Research on concurrent min heaps for multi-threaded priority queues.

References

• Williams, J. W. J., "Algorithm 232: Heapsort," Communications of the ACM, vol. 7, no. 6, 1964, pp. 347-348.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C., "Introduction to Algorithms," 3rd ed., MIT Press, 2009, pp. 155-175.
• Fredman, M. L. and Tarjan, R. E., "Fibonacci heaps and their uses in improved network optimization algorithms," Journal of the ACM, vol. 34, no. 3, 1987, pp. 596-615.
• Knuth, D. E., "The Art of Computer Programming, Volume 3: Sorting and Searching," 2nd ed., Addison-Wesley, 1998, pp. 140-165.
• Tarjan, R. E., "Data Structures and Network Algorithms," SIAM, 1983, pp. 75-90.