Definition

A Heap is a complete binary tree where "parent is always greater (max-heap) or smaller (min-heap) than children". This rule ensures the root always contains the maximum (or minimum) value.

Key Characteristics

• ✓Complete Binary Tree: All levels except the last are fully filled, filled from left to right.
• ✓Heap Property: In max-heap parent ≥ children, in min-heap parent ≤ children, always satisfied.
• ✓Array Implementation: Children of index i are at 2i+1, 2i+2; parent at (i-1)/2.
• ✓Root Access O(1): Max/min value is always at root (index 0) for immediate access.

Time Complexity