Heaps – Efficient Prioritization with Binary Trees

Imagine managing a to-do list where you always want the highest priority task or the smallest number—instantly. That’s what heaps are made for. They’re specialized tree-based structures that let us find the minimum or maximum element quickly, and they’re the backbone of priority queues.

We briefly introduced heaps in our Trees post as a type of specialized binary tree. In this post, we’ll expand on that introduction by exploring how heaps are implemented, where they’re used, and how they differ from another tree-based structure we promised to cover: the Binary Search Tree (BST).

What is a Heap?

A heap is a special kind of binary tree that satisfies the heap property:

  • Min-Heap: The parent node is always less than or equal to its children.
  • Max-Heap: The parent node is always greater than or equal to its children.

Only one rule matters: every parent is ordered with respect to its children—not the entire tree. This is the heap property!

Python Example Using heapq (Min-Heap)

import heapq

# Create an empty heap and push items
heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)

# Always returns the smallest element
print(heapq.heappop(heap))  # Output: 1

Note: Python’s heapq implements a min-heap. To simulate a max-heap, push negative numbers or use custom wrappers.

Heap vs Binary Search Tree (BST)

It’s easy to confuse a heap with a binary search tree, but they serve different purposes:

Feature Heap Binary Search Tree (BST)
Order property Parent-child only Entire left < parent < right
Use case Priority queue, quick min/max Fast searching, insertion, deletion
Balanced structure Not necessarily Often balanced (via AVL/Red-Black)
Lookup time O(n) O(log n) average
Insert/Delete time O(log n) O(log n) average

BSTs are search-oriented: they help you find any value efficiently. Heaps are priority-oriented: they help you find the highest or lowest value fast. You can explore more about BSTs in our Trees post, which covers tree traversal and structure in depth.

Heap Under the Hood: Arrays as Trees

Heaps are usually stored in arrays, not actual tree structures:

  • For any element at index i:
    • Left child: 2i + 1
    • Right child: 2i + 2
    • Parent: (i - 1) // 2

This allows heap operations (insert, delete min/max) to run in O(log n) time.

Use Cases for Heaps

  • Priority Queues: Task schedulers, CPU jobs, event queues
  • Dijkstra’s Algorithm: Pick the next closest node quickly (see Dijkstra)
  • Greedy Algorithms: Always choosing the smallest/largest available item
  • Heapsort: A sorting algorithm that builds a heap, then repeatedly extracts the min/max

Performance Summary

Operation Time Complexity
Insert O(log n)
Remove Min/Max O(log n)
Peek Min/Max O(1)
Build Heap (from array) O(n)

Heaps balance speed and structure, making them ideal for dynamic datasets where priorities change and elements need to be accessed quickly.

Min-Heap vs Max-Heap

Heap Type Returns Use Cases
Min-Heap Smallest element Dijkstra’s, A*, task schedulers
Max-Heap Largest element Leaderboards, cache eviction

Challenge Time! ⏳

  • Implement your own min-heap class using an array.
  • Add support for insert, remove_min, and peek_min.
  • Bonus: Try converting your min-heap into a max-heap.

Coming up next in CQH102: a deeper dive into Tries, where we’ll optimize searching in strings and dictionaries!