The Heap Property & Heapify
You'll learn to
- -Explain the heap property for a min-heap and a max-heap
- -Represent a binary heap in a flat array using index arithmetic
- -Explain what "heapify" (sift-up / sift-down) does and why it keeps the heap valid
Every structure so far in this tier answers a different question - the stack and queue answer "in what order," the hashmap answers "does this key exist," the linked list answers "how do I insert cheaply," binary search answers "where is this." A heap answers yet another one: "what is currently the smallest, or largest, item," instantly, even as items are constantly added and removed.
The Heap Property
A heap is a binary tree with exactly one structural rule, not full sorting - which is precisely what makes it far cheaper to maintain than keeping an entire collection perfectly ordered. A min-heap requires every parent node to be less than or equal to both of its children, so the smallest element overall always sits at the root. A max-heap flips that requirement, so the largest element always sits at the root. Crucially, sibling nodes have no required relationship to each other at all - only the parent-child relationship is constrained, and that single relaxation is exactly what makes a heap cheaper to maintain than a fully sorted array.
Representing a Heap in a Flat Array
Rather than actual Node objects with left and right pointers, a binary heap is almost always stored as a plain array, using index arithmetic to derive parent-child relationships without any pointers at all: for a node at index i, its left child lives at index 2 * i + 1, its right child at 2 * i + 2, and, going the other direction, its parent lives at index (i - 1) // 2. This works because a heap is always kept "complete" - every level fully filled from left to right before the next level starts - so there are never gaps to represent.
Heapify: Restoring the Heap Property
"Heapify" is the umbrella term for fixing a heap-property violation at one spot by moving that single element up or down until it lands where it belongs - it never needs to re-sort or even touch the whole array, only the one path from the violation to its correct resting place.
- -Sift-up (bubble-up): used after inserting a new element at the end of the array - compare it to its parent, and if it violates the heap property, swap them and repeat, walking up the tree at most log n times, the height of a complete binary tree holding n nodes.
- -Sift-down (bubble-down): used after removing the root - move the smaller (or larger) of the current node's two children up into the gap, and repeat down the tree, also at most log n swaps.
That O(1) peek is really the whole point of a heap. A plain sorted array also gives O(1) access to the minimum or maximum element, but keeping it fully sorted costs O(n) per insertion, since everything may need to shift. A heap gives up full ordering to get O(log n) insertion instead, while still answering "what is smallest right now" instantly.