binary heap

A complete binary tree stored in an array in which every parent is ordered before its children, so the smallest (or largest) item is always at the root.

In more detail

Because the tree is complete, the children of index i sit at 2i + 1 and 2i + 2, with no pointers needed. Insert and remove-root each cost O(log n), and reading the root costs O(1). Heap sort builds a heap and then removes the root n times, O(n log n) with no extra memory.

Related terms

Taught in

References