Binary Heap as a Tree — Heap Property Visualization

Binary Heap as a Tree

A binary heap is a complete binary tree that satisfies the heap property: in a max-heap, every parent is greater than or equal to its children; in a min-heap, every parent is less than or equal to its children.

Max-Heap Example

Tree view:              Array: [90, 70, 80, 30, 50, 60, 40]
       90
      /  \
    70    80
   / \   / \
  30 50 60 40

Parent of i: floor((i-1)/2)
Left child of i: 2i + 1
Right child of i: 2i + 2

Min-Heap Example

       10
      /  \
    20    15
   / \   / \
  30 25 50 40

Every parent ≤ its children

Heap Operations

Insert (Bubble Up / Sift Up):

1. Add the new element at the end (next available position)
2. Compare with parent; if it violates the heap property, swap with parent
3. Repeat until the property is restored or the root is reached
4. Time: O(log n)

Extract Max/Min (Bubble Down / Sift Down):

1. Remove the root (max or min element)
2. Move the last element to the root position
3. Compare with children; swap with the larger (max-heap) or smaller (min-heap) child
4. Repeat until the property is restored
5. Time: O(log n)

Heapify (Build Heap):

1. Start from the last non-leaf node (index n/2 - 1)
2. Sift down each node
3. Time: O(n) — not O(n log n) due to the decreasing height of subtrees

Why Complete Binary Tree?

The complete binary tree structure ensures:

• Minimum height for the number of nodes: O(log n)
• Efficient array representation with no wasted space
• O(1) access to the last element for insert/delete

Heap vs BST

Property	Heap	BST
Ordering	Parent vs children only	Left < parent < right
Structure	Complete binary tree	Any shape
Find min/max	O(1)	O(h)
Search	O(n)	O(h)
Insert	O(log n)	O(h)