AIOJ

A heap is a tree in which every node's key is greater than or equal to, or less than or equal to, its parent's key.

A heap in which every node's key is greater than or equal to its parent's key is called a min-heap; otherwise it is called a max-heap. STL's priority_queue is in fact a max-heap.

The main operations supported by a (min-)heap are: inserting a number, querying the minimum, deleting the minimum, merging two heaps, and decreasing the value of an element.

Some powerful heaps (mergeable heaps) can also efficiently support operations such as \.

Even more powerful heaps also support persistence, meaning that any historical version can be queried or operated on to produce a new version.

Heap classifications

Operation Data structure¹	Pairing heap	Binary heap	Leftist tree	Binomial heap	Fibonacci heap
Insert (insert)	$O(1)$	$O(\log n)$	$O(\log n)$	$O(\log n)$ ²	$O(1)$
Find minimum (find-min)	$O(1)$	$O(1)$	$O(1)$	$O(1)$ ³⁴	$O(1)$
Delete minimum (delete-min)	$O(\log n)$ ⁴	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$ ⁴
Merge (merge)	$O(1)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$
Decrease an element's value (decrease-key)	$o(\log n)$ (lower bound $\Omega(\log \log n)$ , upper bound $O(2^{2\sqrt{\log \log n}})$ )⁴	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(1)$ ⁴
Supports persistence	$\times$	$\checkmark$	$\checkmark$	$\checkmark$	$\times$

By convention, an unqualified reference to a “heap” usually means a binary heap.

Footnotes

Table from Wikipedia ↩
The complexity of a single insertion is $O(\log n)$ , but for $k$ consecutive insertions, a binomial heap containing only the elements to be inserted can be created and then merged with the original binomial heap, giving an amortized complexity of $O(1)$ . ↩
A pointer to the minimum element can be maintained, and that pointer can be updated during other operations, allowing queries in $O(1)$ time. ↩
Amortized complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵

heap overview

Heap classifications

Footnotes