Insert
Extract root
Delete
Update key
Build from array
Heap tree representation
Array representation
Operation explanation
Concept reference
Binary heap
A complete binary tree whose parent is always ordered before its children. A min heap keeps the smallest key at the root; a max heap keeps the largest.
Defining rules
- Every level is full except possibly the last.
- The last level fills from left to right.
- Parent index is ⌊(i − 1) / 2⌋; children are 2i + 1 and 2i + 2.
Complexity
Peek is O(1). Insert, extract, update, and delete are O(log n). Building a heap bottom-up is O(n).
Tradeoffs & mistakes
Heaps provide fast access only to the root, not ordered traversal. Common errors include breaking completeness or restoring order in the wrong direction.
Indices begin at 0. Changing heap type rebuilds the ordering rule for the existing values.