A heap is a complete binary tree stored as an array, where every parent satisfies the heap property: in a max-heap, every parent is ≥ its children, so the root is always the maximum. This makes finding the maximum O(1) — just look at index 0.
The heap's power is in its O(log n) insert and extract operations. It is the most efficient data structure for repeatedly finding and removing the largest (or smallest) element, which is exactly what a priority queue needs.
Max-heap: every parent ≥ both children at every level. This doesn't mean the array is fully sorted — a heap is partially ordered. The only guarantee is that the root is the maximum.
Array storage — no pointers For node at index i: parent is at floor((i-1)/2), left child at 2i+1, right child at 2i+2. A complete binary tree fits perfectly into a contiguous array with zero pointer overhead. Very cache-friendly.
Add new element at the end (maintain complete tree shape), then swap with parent while parent is smaller. In the worst case this bubbles up log n levels — the tree height.
Extract max: sift down O(log n) Swap root with last element, remove last (the old root), then sift the new root down by swapping with the larger child until heap property is restored. Also O(log n).
TIPInsert a large number like 99 and watch it sift all the way up to the root. Then extractMax and watch the replacement value sift down. The tree visual and the array view update together — they're the same data structure.