The Heap Property

A binary heap is an array-backed binary tree with one rule:

Min-heap: every node ≤ its children. Max-heap: every node ≥ its children.

          1                   max-heap:
         / \                       9
        3   5                      / \
       /\  /\                     7   8
      4 8 6 10                   /\ /\
                                 6 5 7 4

Stored in an array (1-indexed for math simplicity, but 0-indexed works too):

arr = [_, 1, 3, 5, 4, 8, 6, 10]   (1-indexed; arr[0] unused)
parent(i) = i // 2
left(i)   = 2*i
right(i)  = 2*i + 1

The heap is not sorted — it's only "loosely sorted" enough that the min (or max) is at the root in O(1).

Operations:

• peek() -> O(1) — root
• push(x) -> O(log n) — append + sift-up
• pop() -> O(log n) — swap root with last, remove last, sift-down

Heaps are the backbone of:

• Priority queues
• Heap sort
• Top-K selection
• Dijkstra's algorithm
• Huffman coding (you saw this earlier)