Binary Heaps

A binary heap is a complete binary tree that satisfies the heap property.

Heap Property

Max Heap: Parent ≥ Children (for all nodes) Min Heap: Parent ≤ Children (for all nodes)

For heap sort, we use a max heap.

Array Representation

Heaps are stored in arrays. For a node at index i:

• Left child: 2i + 1
• Right child: 2i + 2
• Parent: ⌊(i-1)/2⌋

Visual Example

Complete Binary Tree

A complete binary tree is filled from left to right at each level. This allows efficient array storage.

Heap Operations

What’s Next?

Now that you understand heaps, let’s learn the heapify operation.