Heaps: A Complete Tree Stored in an Array

A binary heap is a binary tree that keeps its smallest item at the root and fills its levels from left to right, which lets it live in a plain array with no links at all. This card covers the two properties that make a tree a heap, the arithmetic that finds a parent or a child from a position in the array, and why a heap is not a sorted array. A heap is the usual way to build a priority queue: a collection that accepts items in any order and always hands back the most urgent one next.

The first property is heap order. In a min-heap, every parent's key is no larger than the keys of its children, so the smallest key sits at the root. A max-heap reverses the rule and keeps the largest at the root. The second property is shape: the tree is complete, meaning every level is full except possibly the last, and the last level fills from the left with no gaps. The tree below holds 1, 3, 5, 7, 4 and 8, and each note gives the node's index, its position in the array.

Completeness is what lets the array replace the links. Reading the tree level by level, left to right, gives the array 1 3 5 7 4 8, and because there are no gaps every position follows one rule. For the item at index i, counting from 0, the parent is at (i - 1) // 2, where // divides and rounds down, and the children are at 2i + 1 and 2i + 2. A run on this heap printed every index with its parent and children, as the table shows.

Heap order is a rule between a parent and its children only, so a heap is not sorted. Here 7 comes before 4 in the array, and the run reported that heap order holds and that the array is not sorted. An organisation chart is a fair picture: every manager outranks the people who report to them, so the most senior person is at the top. The likeness breaks across a level. Two colleagues on the same level are in no fixed order, and neither are a manager in one department and a junior in another; a heap promises nothing about such pairs either. That weaker promise is cheap to keep, and it still answers the one question a priority queue asks: which item is smallest.

Every operation either reads the root or walks one path between the root and a leaf, and a complete tree of n items has a height of about log2 n, so the costs are these.