Why store a binary heap in an array instead of with pointers?

A binary heap is a nearly complete binary tree, so its nodes map cleanly onto consecutive array indices: a node at index i has children at 2i and 2i+1. This avoids pointer overhead, improves cache behavior, and makes navigation simple arithmetic.

When are Fibonacci heaps worth their complexity?

Fibonacci heaps give O(1) amortized decrease-key, which improves the asymptotic running time of algorithms like Dijkstra's shortest paths on dense graphs. In practice their large constant factors mean simpler binary heaps are often faster, so they matter mainly for theoretical bounds and specialized cases.

Heaps and Priority Queues

A priority queue is an abstract data type that always yields the element of highest (or lowest) priority; heaps are the standard tree-based structures that implement it with efficient insertion and extract-min operations.

Definition

A priority queue is an abstract data type supporting insertion of elements with priorities and extraction of the highest-priority element; a heap is a tree-based data structure satisfying the heap property — every node's key is ordered consistently relative to its children — that implements a priority queue efficiently.

Scope

This topic covers the priority-queue ADT and its heap implementations: the binary heap and its array representation, the heap property and the sift-up/sift-down operations, heapsort, and advanced mergeable heaps such as binomial and Fibonacci heaps that improve key-decrease and union costs. It connects to graph algorithms (Dijkstra, Prim) and event-driven simulation, which rely on priority queues.

Core questions

What operations define the priority-queue ADT, and how does a heap implement them?
How does the heap property allow find-min in constant time and insert/extract in logarithmic time?
How is a binary heap stored compactly in an array, and how is one built in linear time?
How does heapsort use a heap to sort in place in O(n log n) time?
When do mergeable heaps such as Fibonacci heaps improve algorithms that decrease keys often?

Key concepts

priority queue ADT
heap property
binary heap
array-based heap representation
sift-up and sift-down
build-heap in linear time
heapsort
Fibonacci and binomial heaps

Key theories

Heap property and array representation: A binary heap is a nearly complete binary tree in which each node's key dominates its children's; it can be stored in an array with implicit parent-child indexing, giving O(log n) insert and extract and O(1) find-min.
Amortized efficiency of Fibonacci heaps: Fibonacci heaps support decrease-key in O(1) amortized time and extract-min in O(log n) amortized time, improving the asymptotic running time of algorithms such as Dijkstra's and Prim's that perform many key decreases.

Clinical relevance

Priority queues are essential infrastructure: they order ready tasks in operating-system schedulers, manage events in discrete-event simulation, drive best-first and A* search, and provide the frontier in Dijkstra's and Prim's algorithms. Heapsort offers an in-place O(n log n) sort with guaranteed worst-case bounds.

History

J. W. J. Williams introduced the binary heap and heapsort in 1964, and Robert Floyd gave the linear-time build-heap procedure shortly after. Binomial heaps (Vuillemin, 1978) and Fibonacci heaps (Fredman and Tarjan, 1987) added efficient merging and amortized decrease-key, sharpening the running times of classic graph algorithms.

Key figures

J. W. J. Williams
Robert W. Floyd
Michael Fredman
Robert Tarjan

Seminal works

williams1964
fredman1987
cormen2009

Frequently asked questions

Why store a binary heap in an array instead of with pointers?: A binary heap is a nearly complete binary tree, so its nodes map cleanly onto consecutive array indices: a node at index i has children at 2i and 2i+1. This avoids pointer overhead, improves cache behavior, and makes navigation simple arithmetic.
When are Fibonacci heaps worth their complexity?: Fibonacci heaps give O(1) amortized decrease-key, which improves the asymptotic running time of algorithms like Dijkstra's shortest paths on dense graphs. In practice their large constant factors mean simpler binary heaps are often faster, so they matter mainly for theoretical bounds and specialized cases.