Heap

Also known as: Binary heap, Max-heap, Min-heap

A heap (usually a binary heap) is a nearly complete binary tree stored in an array that satisfies the heap order: parent $\le$ children (min-heap) or $\ge$ (max-heap).

insert and extract-min / extract-max are $O(\log n)$; peek is $O(1)$; build-heap is $O(n)$. It is the default priority queue in courses and the structure behind heapsort, Dijkstra, and Huffman.

Not sorted end-to-end: only the root is guaranteed extreme. For ordered iteration use a balanced BST or sort explicitly.

← Back to CS Glossary