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.
Heap Property and Array Representation is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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')Array Representation of a Heap
The complete binary tree structure allows a heap to be stored in a plain array without any pointers. For a node at index i (0-indexed), its parent is at (i-1) // 2, its left child at 2i+1, and its right child at 2i+2. This integer arithmetic replaces pointer traversal and makes heaps extremely cache-friendly.
# Array representation (0-indexed):
# Index: 0 1 2 3 4 5 6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree: 1 (index 0)
# / \
# 3 2 (indices 1, 2)
# / \ / \
# 7 4 5 6 (indices 3,4,5,6)
# Index formulas (0-based):
def parent(i): return (i - 1) // 2
def left_child(i): return 2 * i + 1
def right_child(i): return 2 * i + 2
heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])Sift-Up: Restoring the Heap After Insert
Sift-up (also called bubble-up or heapify-up) is used after inserting a new element at the end of the heap array. Compare the new element with its parent; if the heap property is violated, swap them and continue upward. Repeat until the element is in the correct position or reaches the root. This runs in O(log n) because the tree height is O(log n).
def sift_up(heap, i):
while i > 0:
p = (i - 1) // 2 # parent index
if heap[p] > heap[i]: # min-heap: parent should be smaller
heap[p], heap[i] = heap[i], heap[p]
i = p
else:
break # heap property restored
# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0) # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap) # 0 should bubble to rootSift-Down: Restoring the Heap After Pop
Sift-down (heapify-down) is used after removing the root. Move the last element to the root, then push it down by repeatedly swapping with the smaller child (for min-heap) until the heap property is restored. This also runs in O(log n). Both sift-up and sift-down are the building blocks of all heap operations.
def sift_down(heap, i, n):
while True:
smallest = i
l = 2 * i + 1 # left child
r = 2 * i + 2 # right child
if l < n and heap[l] < heap[smallest]:
smallest = l
if r < n and heap[r] < heap[smallest]:
smallest = r
if smallest == i:
break # already in correct position
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap) # valid min-heap againBuilding a Heap from Array: Floyd's Algorithm
Naively inserting n elements one by one is O(n log n). Floyd's heapify algorithm builds a heap in O(n) by applying sift-down on every non-leaf node, starting from the last non-leaf (index n//2 - 1) and working backward to the root. Leaf nodes are already trivial heaps, so we only need to fix the internal nodes — this is why the total work sums to O(n) rather than O(n log n).
def build_heap(arr):
n = len(arr)
# Start from last non-leaf node: index n//2 - 1
for i in range(n // 2 - 1, -1, -1):
sift_down(arr, i, n)
return arr
arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr) # root should be 1
# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).Heap Sort Using the Array Heap
Heap sort runs in O(n log n) with O(1) extra space. Phase 1: build a max-heap from the array in O(n). Phase 2: repeatedly extract the maximum by swapping the root with the last unsorted element, then sift-down on the reduced heap. After n extractions, the array is sorted in ascending order. This in-place algorithm demonstrates how the array representation enables sorting without allocating a separate data structure.
def sift_down_max(arr, i, n):
while True:
largest = i
l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[largest]: largest = l
if r < n and arr[r] > arr[largest]: largest = r
if largest == i: break
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
def heap_sort(arr):
n = len(arr)
# Build max-heap
for i in range(n // 2 - 1, -1, -1):
sift_down_max(arr, i, n)
# Extract elements one by one
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0] # move max to end
sift_down_max(arr, 0, end)
arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr) # [1, 2, 3, 5, 7, 8, 9]Min-Heap vs Max-Heap
A min-heap has the smallest element at the root; popping always gives the minimum. A max-heap has the largest element at the root; popping always gives the maximum. Both have identical structure and operations — only the comparison direction changes. Python's heapq module implements a min-heap only, so you must negate values to simulate a max-heap.
import heapq
# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap)) # 1
# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
heapq.heappush(max_heap, -val) # negate on push
print('Max-heap max:', -heapq.heappop(max_heap)) # 5 (negate on pop)
# For tuples: heapq sorts by first element
print(min_heap, max_heap)Heap Operations Complexity Summary
All heap operations derive from sift-up and sift-down, both O(log n). Push: append + sift-up = O(log n). Pop: swap root with last + sift-down = O(log n). Peek: access index 0 = O(1). Build heap: O(n) via Floyd's algorithm. Heap sort: O(n log n). These complexities make heaps the ideal structure when you repeatedly need the minimum or maximum of a dynamic collection.
# Heap complexity summary:
# Operation | Time | Space
# --------------|------------|-------
# Push | O(log n) | O(1)
# Pop (min/max) | O(log n) | O(1)
# Peek | O(1) | O(1)
# Build from n | O(n) | O(1) in-place
# Heap sort | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)
import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data)) # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data)) # [1, 2, 3]Practical Heap Patterns in Interviews
Heaps solve a family of interview problems with a common pattern: maintain a priority queue of k candidates while streaming through n elements. Top-k frequent elements, k closest points to origin, and task scheduler all use this pattern. Recognise it when you see: 'given a stream of n items, maintain the k best' — this always calls for a heap of size k, giving O(n log k) total time.
import heapq
# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
# Use max-heap (negate distance) of size k
heap = []
for x, y in points:
dist = -(x*x + y*y) # negate for max-heap
heapq.heappush(heap, (dist, x, y))
if len(heap) > k:
heapq.heappop(heap) # remove farthest
return [[x, y] for _, x, y in heap]
points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2)) # 2 closest to originHeap vs Sorted Array Trade-offs
Choose a heap when you only need repeated access to the minimum or maximum and the collection changes dynamically. Choose a sorted array when you need random access by index or range queries. The heap's weakness is that it gives O(n) search for arbitrary elements; its strength is O(log n) insert/delete and O(1) min/max access. A sorted array has O(n) insert but O(log n) search via binary search.
# Trade-off comparison:
# Structure | insert | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap | O(logn) | O(logn) | O(n) | O(n)
# Sorted array | O(n) | O(n) | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn) | O(logn)| O(logn+k)
# Hash map | O(1) | O(1) | O(1) | O(n)
# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: the heap property and complete binary tree structure, array representation with parent/child index formulas, and sift-up and sift-down as the building blocks for all heap operations including Floyd's O(n) build. Next up we implement heapify and explore Python's heapq module.
Frequently asked questions
Is the “Heap Property and Array Representation” lesson free?
Yes — the full text of “Heap Property and Array Representation” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Heap Property and Array Representation” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Heap Property and Array Representation
- Heapify, Push, and Pop from Scratch
- Python heapq and Max-Heap Tricks
- Median from Data Stream and K-Way Merge