Max Heap

Definition and Characteristics

Definition

Max heap: complete binary tree where each node ≥ children. Root node holds maximum element. Structure supports priority-based access.

Characteristics

Complete binary tree: all levels filled except possibly last, filled left to right. Ensures balanced height O(log n).

Key Properties

Max-heap property, complete shape, array-based storage, efficient max retrieval, dynamic updates supported.

Heap Property

Max-Heap Property

For every node i except root, A[parent(i)] ≥ A[i]. Guarantees maximum at root.

Consequence

Partial order: no total order among siblings or subtrees. Max element always accessible in O(1) time.

Violation and Restoration

Insertion or deletion may violate property. Fix using heapify or sift-up/down operations.

Structure and Representation

Binary Tree Form

Complete binary tree: height h = ⌊log₂ n⌋. Node positions fixed by level-order.

Array Representation

Array A indexed 1 to n. Parent(i) = ⌊i/2⌋, left child = 2i, right child = 2i+1.

Advantages

Memory compactness: no explicit pointers. Fast index computations for parent/child. Cache-friendly layout.

Core Operations

Find Maximum

Access root element at A[1]. Time: O(1).

Insertion

Add element at next available position. Restore heap property via sift-up.

Deletion of Maximum

Remove root. Replace with last element. Restore heap property via sift-down.

Heapify

Build heap from unordered array. Restore property bottom-up.

Insertion Algorithm

Stepwise Procedure

1. Add element at end (next free leaf). 2. Compare with parent; if greater, swap. 3. Repeat until heap property restored or root reached.

Complexity

Time: O(log n), path length from leaf to root. Space: O(1) auxiliary.

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

Removing Maximum

Remove root element. Replace with last element in heap.

Restore Heap Property

Sift-down: compare with children; swap with larger child if needed. Repeat till property restored.

Complexity

Time: O(log n). Space: O(1).

Pseudocode

function extractMax(heap): if heap.size < 1: return error max = heap[1] heap[1] = heap[heap.size] heap.size -= 1 maxHeapify(heap, 1) return max

Heapify Process

Definition

Convert subtree rooted at index i into max heap assuming subtrees already heaps.

Algorithm

Compare node with children; swap with largest child if node smaller; recurse.

Build-Max-Heap

Apply maxHeapify from last non-leaf node down to root.

Pseudocode

function maxHeapify(heap, i): l = left(i) r = right(i) largest = i if l ≤ heap.size and heap[l] > heap[i]: largest = l if r ≤ heap.size and heap[r] > heap[largest]: largest = r if largest != i: swap(heap[i], heap[largest]) maxHeapify(heap, largest)

Time Complexity

O(log n) per call. Build-Max-Heap overall O(n).

Time and Space Complexity

Insertion

O(log n) time. O(1) space.

Deletion

O(log n) time. O(1) space.

Find-Max

O(1) time.

Build-Heap

O(n) time using bottom-up heapify.

Space Complexity

O(n) for storing n elements. Auxiliary O(1).

Applications of Max Heap

Priority Queues

Max heap underlies priority queue implementation. Allows quick access to highest priority element.

Heap Sort

Sort array in O(n log n) using max heap for repeated max extraction.

Graph Algorithms

Used in Dijkstra’s algorithm, Prim’s MST for priority management.

Real-Time Systems

Efficient scheduling based on task priorities.

Median Maintenance

Combined with min heap to maintain dynamic medians.

Comparison with Min Heap

Heap Property

Max heap: parent ≥ children. Min heap: parent ≤ children.

Use Cases

Max heap: max-priority retrieval. Min heap: min-priority retrieval.

Implementation

Identical structure; only comparison operators differ.

Time Complexity

Same for all operations: insertion, deletion, heapify.

Example

Implementation Details

Array-Based Storage

Allocate array size n. Keep track of heap size. Index arithmetic for navigation.

Insertion and Deletion Code Snippets

Use sift-up for insertion, sift-down for deletion.

Memory Considerations

Static arrays or dynamic arrays (vectors). Dynamic resizing may be needed.

Language Support

Standard libraries provide priority queues implemented as heaps (e.g., C++ STL, Java PriorityQueue).

Heap Sort Using Max Heap

Algorithm Overview

1. Build max heap from unsorted array. 2. Swap root with last element. 3. Reduce heap size. 4. Heapify root. Repeat.

Complexity

Time: O(n log n). Space: O(1) in-place sort.

Pseudocode

function heapSort(array): buildMaxHeap(array) for i from array.length down to 2: swap(array[1], array[i]) heapSize -= 1 maxHeapify(array, 1)

Advantages

In-place, no additional memory. Consistent O(n log n) worst-case performance.

Limitations

Not stable. More data movement compared to quicksort.

References

• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., Introduction to Algorithms, MIT Press, 3rd Ed., 2009, pp. 155-194.
• Knuth, D.E., The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 2nd Ed., 1998, pp. 400-440.
• Williams, J.W.J., Algorithm 232: Heapsort, Communications of the ACM, vol. 7, no. 6, 1964, pp. 347-348.
• Fredman, M.L., 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.
• Weiss, M.A., Data Structures and Algorithm Analysis in C++, Pearson, 4th Ed., 2013, pp. 220-270.