DSA Interview Prep · Lesson

Heap Property and Array Representation

Understand the complete-binary-tree structure stored as an array, derive parent/child index formulas, and visualise sift-up and sift-down operations.

What is a Heap?

A heap is a specialised complete binary tree that satisfies the heap property: in a min-heap, every parent is smaller than or equal to its children; in a max-heap, every parent is larger than or equal to its children. This property guarantees that the minimum (or maximum) element is always at the root, enabling O(1) access to the extremal element. Heaps are the data structure behind priority queues.

# Min-heap example:
#         1
#        / \
#       3   2
#      / \ / \
#     7  4 5  6
# Every parent <= its children
# Root (1) is always the minimum

# Max-heap example:
#         9
#        / \
#       7   8
#      / \ / \
#     3  4 5  6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')

Complete Binary Tree Structure

A heap is stored as a complete binary tree — all levels are fully filled except possibly the last, which is filled from left to right. This structure is what enables the elegant array representation with no wasted space and no pointers. The complete property ensures that the heap's height is always floor(log₂ n), guaranteeing O(log n) push and pop operations.

# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))

# NOT complete (last level not left-filled):
#     1
#    / \
#   2   3
#        \
#         4  <- right child without left sibling

# Valid complete binary tree with 4 nodes:
#     1
#    / \
#   2   3
#  /
# 4
print('Complete BT: height = floor(log2(n)) always')

All lessons in this course

← Back to DSA Interview Prep