Skip to main content

Heaps

Premium

A heap is a specialized tree-based data structure that satisfies the heap property, for a min-heap, each parent node is smaller than its children; for a max-heap, each parent node is larger than its children.

Heaps are efficient for problems involving frequent retrieval of the smallest or largest element, such as priority scheduling, graph algorithms, and streaming data.

heap

Types of heaps

1. Min heap

A min heap ensures that the smallest element is always at the root. Each parent node is less than or equal to its children.

Min heap

Used for:

  • Dijkstra’s shortest path algorithm
  • Prim’s minimum spanning tree
  • Priority scheduling
  • Finding the k smallest elements

2. Max heap

A max heap ensures that the largest element is always at the root. Each parent node is greater than or equal to its children.

Max heap

Used for:

  • Heapsort
  • Priority queues for max values
  • Finding the k largest elements

Common operations for heaps

1. Insert & extract from heap

import heapq heap = [] heapq.heappush(heap, 10) heapq.heappush(heap, 5) print(heapq.heappop(heap)) # removes and returns 5 (smallest)

Heaps TC

Common edge cases & pitfalls

  1. Forgetting to invert values when using Python’s heapq for a max-heap

  2. Confusing heap with sorted array, heap only guarantees order at the root

  3. Modifying heap directly (e.g., deleting non-root elements) can break the heap property

  4. Heapify after modifying the underlying list to restore order

  5. Remember: searching arbitrary elements is O(n), not O(log n)

Calculating memory usage

Since they are typically represented by an array, heaps have little memory overhead besides the size of the array itself. In fact, heaps rely on an in-place sorting algorithm known as heapsort, so you can actually build a heap using an existing array and no additional memory!

Quiz

  1. What is the time complexity of inserting into a heap?

a) O(1)

b) O(log n)

c) O(n)

d) O(n log n)

  1. Which data structure is commonly used to implement a priority queue?

a) Stack

b) Linked List

c) Heap

d) Queue

  1. What is the time complexity of building a heap from an unsorted array?

a) O(n log n)

b) O(log n)

c) O(n)

d) O(1)

Practice problems

  1. Largest numbers
  2. Buy sell stock
  3. Find median from data stream
Next Lesson