Heap data structure

In a max-heap, a parent key is no smaller than its children’s keys, making the root maximal. A min-heap reverses the comparison. Siblings and entire levels need not be sorted, so heap order is weaker than a fully sorted sequence.

A binary heap also has a complete-tree shape, filling levels and placing the final level to the left. With a one-based array, position k has parent floor(k/2) and children 2k and 2k+1, representing links through index arithmetic.

References: [1]

Insertion places an item at the array’s end, then swims it upward while it exceeds its parent in a max-heap. The complete-tree shape remains intact while order is repaired along one ancestor path.

Removing the maximum replaces the root with the final item, then sinks it by exchanging with the larger child as needed. The path is logarithmic. Resizing the backing array adds copying that must be accounted for separately through amortized analysis.

References: [1]

An existing batch can be heapified without inserting every element separately. Sinking internal nodes from the bottom upward uses already-heap-ordered child subtrees and builds a binary heap in linear total time, unlike the general bound for repeated insertion.

Ordering also depends on valid comparisons. Changing a stored item’s key externally without repairing the structure can invalidate the root’s guarantee. This data structure commonly implements priority queues and is distinct from the runtime storage region also called a heap.

References: [1]