Heap data structure

A tree-based data structure that orders each parent relative to its children so that an extremal value is available at the root. In a max-heap, every parent is at least as large as its children. Heap implementations provide one way to realize a priority queue; the abstract queue and its implementing structure are distinct concepts.

A Fibonacci heap implements a meldable priority queue using a collection of heap-ordered trees and a pointer to a minimum. Insertion and melding defer consolidation. Removing the minimum promotes its children and repeatedly links roots with equal numbers of children, keeping the smaller key above the larger. Decreasing a key cuts a violating node; mark bits and cascading cuts control how much child loss a retained node may accumulate.

The potential method charges stored work using the number of tree roots plus twice the number of marked nodes. It yields constant amortized cost for insertion, melding and decrease-key, and $O(\log n)$ for removing the minimum. These are sequence guarantees, not worst-case bounds for each operation. A node with $k$ children has at least a Fibonacci-sized subtree, bounding $k$ logarithmically in total heap size. The inexpensive decrease-key operation improves Dijkstra's algorithm to $O(m+n\log n)$ with adjacency lists.^[ref]

A heap data structure stored as a complete rooted tree with up to $d$ children per vertex, where $d\ge 2$. The final level is filled from left to right. For zero-based array storage, the parent of entry $i>0$ is $\lfloor (i-1)/d\rfloor$, and its child number $j\in \{0,\dots ,d-1\}$ has index $di+j+1$ when that index is inside the active heap. There are at most $O(1+{\log }_{d}n)$ levels containing $n$ entries.

A d-ary heap in which each parent key is no greater than each child key. Transitivity makes the root a minimum. Removing the root requires choosing a smallest child at each downward step, taking $O(d{\log }_{d}n)$ time in the usual $2\le d\le n$ range. Decreasing a key or inserting a new leaf only compares along one chain of parents, taking $O({\log }_{d}n)$ time in that range. These priority queue bounds assume constant-time key comparisons and available array capacity. An indexed priority queue must also update its item-to-index table after every swap.

A heap data structure supporting a meld operation that combines two heaps into one while preserving the heap order. The cost of melding distinguishes implementations such as a leftist heap from ordinary binary heaps.

A meldable heap satisfying the min-heap ordering: each parent key is no greater than its children's keys. It combines efficient merging with access to the current minimum key.

A binary meldable heap satisfying heap order and the leftist condition: at each node, the shortest path to a missing child is no longer in the right subtree than in the left. Melding recurses down right spines, swaps children when needed, and takes logarithmic time.

A heap data structure in which every parent key is at least as large as its children's keys. The root therefore stores a largest key, allowing a priority queue to retrieve a current maximum efficiently.

A min-heap has every parent key no greater than its child keys. The root therefore contains a minimum key.