The Heap Property & Heapify

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.

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.

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" 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.