Binary Heap — Definition, Formula & Example
A binary heap is a tree-shaped way of storing numbers so the smallest (or largest) one always sits at the top. That lets you find it instantly, and adding or removing a value takes only a few swaps.
A binary heap is a complete binary tree whose nodes hold keys from an ordered set and satisfy the heap property. In a min-heap, every node's key is less than or equal to the keys of its children. In a max-heap, every node's key is greater than or equal to its children's keys. Because the tree is complete, it is stored as an array with no gaps. With zero-indexing, node has children at and .
Key Formula
Where:
- = Zero-based array index of a node (the root is at index 0)
- = Floor function: round down to the nearest integer
Worked Example
Problem: The min-heap stored as the array [10, 20, 30, 40, 50, 60] (indices 0 to 5) receives a new key, 5. Insert it and restore the heap property.
Step 1: Place 5 in the next open slot, index 6. This keeps the tree complete. Its parent is at index 2, which holds 30. Since , swap them.
Step 2: Now 5 sits at index 2. Its parent is at index 0, which holds 10. Since , swap again.
Step 3: Key 5 is now the root, so sift-up stops. Check each parent against its children: index 0 has children at indices 1 and 2, index 1 has children at 3 and 4, and index 2 has children at 5 and 6.
Answer: The new heap is [5, 20, 10, 40, 50, 60, 30]. Insertion took 2 swaps, which equals the tree's height of 2. Each swap moves the new key up one level, so insertion costs at most swaps for nodes.
Why It Matters
Binary heaps are the standard way to build a priority queue. A priority queue drives Dijkstra's shortest-path algorithm and Prim's minimum spanning tree algorithm in a discrete math or algorithms course. Heapsort uses the same structure to sort items in time without extra memory.
Common Mistakes
Mistake: Assuming a heap's array is sorted, or that left children are smaller than right children as in a binary search tree.
Correction: The heap property only compares a parent with its own children. Siblings and cousins can be in any order. In the example, 20 sits to the left of 10, which is allowed. Only the root is guaranteed to be the minimum (or maximum).
