Heaps and Priority Queues Guide with Heap Sort
A heap is a specialized tree-based data structure that satisfies the heap property. In a max-heap, every parent node is greater than or equal to its children, placing the maximum element at the root. In a min-heap, every parent is less than or equal to its children, placing the minimum at the root. Heaps are the standard implementation of priority queues and appear in algorithms from Dijkstra’s shortest path to heap sort, making them one of the most versatile data structures in computer science.
The heap is notable for its efficiency in dynamic scenarios where elements are continuously added and the extreme element must be retrieved. Unlike sorting the entire collection after each insertion at O(n log n), a heap maintains the extreme element in O(log n) per operation with O(1) space overhead beyond the elements themselves. This efficiency makes heaps indispensable for real-time systems, event-driven simulations, streaming algorithms, and any application where priorities change dynamically.
The Heap Property
Max-Heap
In a max-heap, every parent is greater than or equal to its children. The root contains the absolute maximum element in the entire structure. Each subtree is itself a valid max-heap, giving heaps a recursive structure that simplifies algorithms. The heap property does not guarantee any ordering between siblings or between nodes at different levels — a node at depth 3 could be larger than a node at depth 2, as long as both satisfy the parent-child relationship.
Min-Heap
In a min-heap, every parent is less than or equal to its children, placing the minimum at the root. Heaps are not fully sorted — the only guarantee is that the root is the extreme element and each parent-child relationship satisfies the heap property. Elements at the same level or in different branches of the tree have no ordering relationship with each other.
Binary Heap Array Representation
Heaps are stored as arrays for efficiency, eliminating pointer overhead and improving cache locality through contiguous memory access. The array layout is a level-order traversal of the complete binary tree — the root at index 0, its children at indices 1 and 2, their children at indices 3 through 6, and so on. For an element at index i, the parent is at (i-1)/2, the left child is at 2i+1, and the right child is at 2i+2. These simple arithmetic formulas enable navigation without storing any pointers, reducing memory overhead by 50 percent compared to a pointer-based tree representation.
Core Operations
Insert
Adding a new element to a heap requires appending it to the end of the array and then bubbling it up by swapping with its parent until the heap property is restored. In a max-heap, the new element swaps with its parent if it is larger, continuing until it reaches a parent that is larger or becomes the root. This operation takes O(log n) time proportional to the height of the tree.
Extract Max or Min
Removing the root element requires replacing it with the last element in the array and then sifting it down by swapping with the larger child for a max-heap or the smaller child for a min-heap. The sift-down operation continues until the heap property is restored, also taking O(log n) time.
Peek
Returning the root element without removing it is O(1), making it efficient to check the current extreme value without modifying the structure. This is the primary advantage of a heap over a sorted array for dynamic datasets.
Heapify
Building a heap from an arbitrary unsorted array is surprisingly O(n), not O(n log n). The heapify algorithm starts from the last non-leaf node in the array and sifts down each node to its correct position. The O(n) bound holds because most nodes are near the bottom of the tree, requiring few sift-down operations — approximately half the nodes are leaves requiring zero sifts, a quarter require at most one sift, and so on. The total work is proportional to n, making heapify significantly faster than inserting elements one by one at O(n log n).
Heap Sort
Heap sort combines heapify with repeated extraction for an in-place, comparison-based sorting algorithm with O(n log n) worst-case time and O(1) extra space. First, the array is heapified in O(n) time. Then, the maximum element is repeatedly swapped with the last element of the unsorted portion and sifted down, placing elements in sorted order from the end of the array. Heap sort guarantees O(n log n) without the worst-case O(n squared) of quicksort, making it suitable for real-time systems where predictable performance is critical.
In practice, heap sort is not as widely used as quicksort or merge sort because its constant factors are higher and it lacks the cache-friendly sequential access patterns of those algorithms. However, it remains the preferred choice when guaranteed O(n log n) worst-case performance is required and memory is constrained, such as in embedded systems and real-time applications.
d-ary Heaps
A generalization of the binary heap is the d-ary heap, where each node has up to d children. Increasing d reduces the height of the tree, making insert operations faster since fewer swaps are needed during bubble-up. However, extract operations become slower since each sift-down must compare d children to find the largest or smallest. A 4-ary heap reduces insert time by approximately 30 percent compared to a binary heap while increasing extract time by approximately 20 percent, which is beneficial for workloads with many more inserts than extracts.
The optimal value of d depends on the ratio of inserts to extracts in the application. For priority queues in Dijkstra’s algorithm where extracts dominate, binary heaps are optimal. For event simulation where inserts dominate, higher-degree heaps provide better throughput.
Heap Variants for Specialized Needs
Several heap variants address limitations of the basic binary heap for specific use cases. Binomial heaps support efficient merging of two heaps in O(log n) time through a forest of binomial trees, making them suitable for applications where heaps need to be combined frequently. Fibonacci heaps provide O(1) insert and decrease-key amortized time with O(log n) extract-min, theoretically optimal for algorithms like Dijkstra that perform many decrease-key operations.
Pairing heaps offer a simpler alternative to Fibonacci heaps with good practical performance, supporting O(1) insert and O(log n) extract-min with simpler implementation. Soft heaps introduce controlled corruption by intentionally merging similar elements, achieving O(1) amortized insert and extract operations at the cost of allowing some elements to have slightly incorrect priority values. These specialized variants are primarily used in academic research and specialized high-performance computing applications.
Priority Queue in Practice
Priority queues are one of the most important abstract data types in software engineering. Operating systems use them for process scheduling based on priority levels, networking for packet queuing with quality-of-service guarantees, graphics for hidden surface removal determining which objects to render, and data compression for Huffman coding where frequency determines priority. The binary heap provides the best balance of performance and simplicity for most priority queue applications, which is why it is the default implementation in Python’s heapq, Java’s PriorityQueue, and C++’s priority_queue.
For applications requiring additional operations beyond insert and extract, specialized heap variants exist. Decrease-key operations that reduce the priority of an existing element are needed in Dijkstra’s algorithm for updating distances. Binary heaps support decrease-key in O(log n) time with an auxiliary hash table mapping elements to their positions. Meldable heaps support combining two heaps into one efficiently.
Applications
Priority queues provide access to the highest or lowest priority element in O(log n) per operation. Dijkstra’s algorithm uses a min-heap to efficiently extract the minimum-distance vertex during shortest-path computation. Median maintenance uses two heaps — a max-heap for the lower half and a min-heap for the upper half — to maintain the running median of a stream in O(log n) per insertion. Top K element problems use a min-heap of size K that discards the smallest element on each insert. Merging K sorted lists uses a min-heap to extract the smallest element across all lists in O(log K) per extraction.
Frequently Asked Questions
What is the difference between a heap and a priority queue? A priority queue is an abstract data type supporting insert and extract-min or extract-max. A heap is a concrete data structure that implements a priority queue efficiently.
Why is heapify O(n) and not O(n log n)? Most elements are near the bottom of the tree requiring few sifts. The sum of all sift operations across all nodes is O(n), not O(n log n).
When should I use a heap versus a sorted array? Use a heap for dynamic insertions and extractions of the extreme element. Use a sorted array for iteration in sorted order with infrequent insertions.
How do I implement a max-heap using a min-heap library? Insert negative values with push instead of the original value, and pop returns the negated value.
What is the median maintenance problem? Maintain the running median of a stream using two heaps: a max-heap for the lower half and a min-heap for the upper half, rebalancing after each insertion.
Stacks and Queues Guide — Hash Tables Guide — Trees and Graphs Guide