DSA Heaps

A heap is a specialized tree-based data structure that satisfies the heap property. It is a complete binary tree — all levels are fully filled except possibly the last, which is filled from left to right. Heaps are primarily used to implement priority queues and are essential for algorithms like Heap Sort and Dijkstra's shortest path.

Types of Heaps

Max Heap

In a max heap, the value of every parent node is greater than or equal to the values of its children. As a result, the maximum element is always at the root.


# Max Heap example:
#         90
#        /  \
#       70   80
#      / \  /
#     40 50 60
# Every parent >= its children

Min Heap

In a min heap, the value of every parent node is less than or equal to the values of its children. The minimum element is always at the root.


# Min Heap example:
#         10
#        /  \
#       20   30
#      / \  /
#     50 40 35
# Every parent <= its children

Heap Representation Using an Array

Heaps are efficiently stored as arrays. Given a node at index i:

  • Left child is at index 2*i + 1
  • Right child is at index 2*i + 2
  • Parent is at index (i - 1) // 2

# Array representation of the max heap:
#         90         Index: 0
#        /  \
#       70   80      Indices: 1, 2
#      / \  /
#     40 50 60       Indices: 3, 4, 5

heap_array = [90, 70, 80, 40, 50, 60]
# Parent of index 3 (value 40): (3-1)//2 = 1 (value 70) ✓
# Left child of index 1 (value 70): 2*1+1 = 3 (value 40) ✓

Python's heapq Module (Min Heap)

Python's heapq module provides a min heap implementation. All operations work on a regular Python list.

Basic Min Heap Operations


import heapq

# Create a min heap
min_heap = []

# heappush — Insert element and maintain heap property
heapq.heappush(min_heap, 30)
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 50)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 20)

print("Heap:", min_heap)        # Output: [5, 10, 50, 30, 20]
print("Minimum:", min_heap[0])  # Output: Minimum: 5

# heappop — Remove and return the minimum element
smallest = heapq.heappop(min_heap)
print("Popped:", smallest)      # Output: Popped: 5
print("New minimum:", min_heap[0])  # Output: New minimum: 10

Building a Heap from an Existing List — O(n)


numbers = [40, 10, 30, 5, 25, 15]
heapq.heapify(numbers)   # Transforms list into a valid min heap in-place
print("Min Heap:", numbers)   # Output: [5, 10, 15, 40, 25, 30]
print("Minimum:", numbers[0]) # Output: Minimum: 5

Simulating a Max Heap with heapq

Python's heapq is a min heap. To simulate a max heap, store values as their negatives.


import heapq

max_heap = []
values = [10, 50, 30, 90, 20]

for val in values:
    heapq.heappush(max_heap, -val)   # Negate values

# Pop the maximum (negate again to restore)
max_val = -heapq.heappop(max_heap)
print("Maximum:", max_val)   # Output: Maximum: 90

Priority Queue Using a Heap

A priority queue serves elements based on their priority, not insertion order. Heaps make this O(log n) per operation.


import heapq

# Each task is (priority, task_name) — lower number = higher priority
task_queue = []
heapq.heappush(task_queue, (3, "Write report"))
heapq.heappush(task_queue, (1, "Fix critical bug"))
heapq.heappush(task_queue, (2, "Review pull request"))
heapq.heappush(task_queue, (1, "Deploy to production"))

while task_queue:
    priority, task = heapq.heappop(task_queue)
    print(f"Priority {priority}: {task}")

# Output:
# Priority 1: Deploy to production
# Priority 1: Fix critical bug
# Priority 2: Review pull request
# Priority 3: Write report

Heap Sort

Heap sort uses a heap to sort data. It first builds a max heap, then repeatedly extracts the maximum element and places it at the end of the array.


def heap_sort(arr):
    heapq.heapify(arr)                  # Build min heap
    return [heapq.heappop(arr) for _ in range(len(arr))]   # Extract in order

data = [64, 25, 12, 22, 11]
print("Sorted:", heap_sort(data))
# Output: Sorted: [11, 12, 22, 25, 64]
  • Time Complexity: O(n log n) for all cases.
  • Space: O(1) for in-place heap sort.

Finding the K Largest or K Smallest Elements

One of the most common real-world heap applications is finding the top-K or bottom-K elements efficiently.


import heapq

numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

# K largest elements
print(heapq.nlargest(3, numbers))    # Output: [9, 6, 5]

# K smallest elements
print(heapq.nsmallest(3, numbers))   # Output: [1, 1, 2]

Big O Summary for Heap Operations

  • Insert (heappush) — O(log n)
  • Remove min/max (heappop) — O(log n)
  • Access min/max — O(1)
  • Build heap (heapify) — O(n)
  • Heap sort — O(n log n)
  • Find K largest/smallest — O(n log k)

Key Points

  • A heap is a complete binary tree that satisfies the heap property (parent ≥ children for max heap; parent ≤ children for min heap).
  • Heaps are stored efficiently as arrays using index formulas for parent and child positions.
  • Python's heapq module implements a min heap on standard lists.
  • To simulate a max heap, negate the values before pushing and after popping.
  • Heaps are the ideal structure for priority queues — O(log n) insert and extract.
  • Common applications include heap sort, finding K largest/smallest elements, and Dijkstra's algorithm.
Previous lessons
Back to courses
Next lessons

Leave a Comment