Heap & Priority Queue

Concept Overview

A heap is a specialized tree-based data structure that satisfies the heap property. It is commonly implemented as a binary heap, in which the tree is a nearly complete binary tree. Heaps are crucially used to implement priority queues, abstract data types where each element has an associated priority, and elements are dequeued according to their priority rather than the order they were enqueued (unlike standard queues).

Mathematical Definition

A binary heap is represented as an array A, where A[0] is the root of the tree. The structural property ensures the tree is completely filled on all levels except possibly the lowest, which is filled from left to right. The heap property determines the order of the keys.

For any node at index i:

Parent(i) = ⌊(i - 1) / 2⌋

LeftChild(i) = 2i + 1

RightChild(i) = 2i + 2

// Max-Heap Property:

For all nodes i (except root): A[Parent(i)] ≥ A[i]

// Min-Heap Property:

For all nodes i (except root): A[Parent(i)] ≤ A[i]

Key Concepts

Heapify Operations

Maintaining the heap property requires structural adjustments when elements are added or removed.Heapify-Up (or bubble-up/sift-up) is used after insertion: a new element is added to the bottom-most, right-most available position to maintain the complete tree property, and then swapped with its parent iteratively until the heap property is restored.Heapify-Down (or bubble-down/sift-down) is used after extracting the root: the last element in the tree replaces the root, and is then swapped with its largest (in a max-heap) or smallest (in a min-heap) child iteratively until the heap property is restored. Both operations run in O(log n) time.

Array Representation

Because a binary heap is a complete binary tree, it can be efficiently represented as a flat array without pointers. This implicit data structure minimizes memory overhead and provides excellent spatial locality, leading to highly efficient cache usage during traversal and manipulation. The implicit indices allow for O(1) time complexity when calculating parent and child relationships.

Build-Heap Algorithm

Constructing a heap from an unordered array of n elements can be done by repeatedly inserting each element, taking O(n log n) time. However, a more optimal bottom-up approach, famously designed by Floyd, achieves O(n) time complexity. It works by calling Heapify-Down on all non-leaf nodes starting from the last internal node up to the root.

Historical Context

The binary heap data structure was invented by J. W. J. Williams in 1964 as a fundamental part of the Heapsort sorting algorithm. His elegant formulation allowed for an efficient, in-place sort that guaranteed O(n log n) time complexity, contrasting with Quicksort's worst-case O(n²) time.

Later that same year, Robert W. Floyd published an improved version of the Build-Heap algorithm, establishing the linear-time construction method that is widely used today. Over time, the heap became recognized independently as the optimal data structure for implementing priority queues.

Real-world Applications

Operating System Schedulers: Priority queues manage tasks and processes, ensuring that higher-priority tasks (e.g., system interrupts) are executed before lower-priority background tasks.
Graph Algorithms: Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm use min-heaps to efficiently find the next closest vertex, reducing their time complexities significantly.
Event-Driven Simulation: Discrete-event simulators maintain a priority queue of future events, ordered by their scheduled execution time.
Data Compression: Huffman coding uses a min-heap to repeatedly merge the two least frequent characters into a tree, constructing an optimal prefix code.
Finding the K-th Largest Element: Maintaining a min-heap of size k allows processing streaming data to find the k largest elements seen so far in O(n log k) time.

Related Concepts

Stack & Queue — standard linear data structures where ordering is strictly based on insertion time rather than an intrinsic value
Sorting — Heapsort relies entirely on the heap data structure
Dijkstra Algorithm — explicitly requires a min-priority queue for optimal execution
Binary Search Tree — another tree structure, but guarantees total ordering (in-order traversal yields sorted elements), whereas heaps only guarantee partial ordering (parent vs child)

Heap & Priority Queue