🎓 A1Learner
🔍

DSA Heaps and Priority Queues

A heap is a tree-shaped structure that keeps the smallest value at the top. A priority queue is a heap used as a to-do list where the most urgent item leaves first.

The smallest sits on top

heappush adds a value and heapq restores the order. The smallest value waits at index zero.

import heapq
heap = []
for v in (5, 2, 8, 1):
    heapq.heappush(heap, v)
print(heap)
print("top:", heap[0])

Pops come out sorted

heappop removes the top value each time. Repeated pops drain the heap in rising order.

import heapq
heap = [5, 2, 8, 1]
heapq.heapify(heap)
out = []
while heap:
    out.append(heapq.heappop(heap))
print(out)

Tuples order by first item

A tuple compares by its first item first. Equal first items compare by the next item.

import heapq
heap = []
heapq.heappush(heap, (2, "b"))
heapq.heappush(heap, (1, "a"))
heapq.heappush(heap, (2, "a"))
print(heapq.heappop(heap))
print(heapq.heappop(heap))

Example

import heapq

tasks = [(3, "water plants"), (1, "fix leak"), (2, "pay bill"), (1, "call tenant")]
heap = []
counter = 0
pushes = 0
pops = 0
for priority, name in tasks:
    heapq.heappush(heap, (priority, counter, name))
    counter += 1
    pushes += 1
print("heap after pushes:", heap)
while heap:
    priority, _, name = heapq.heappop(heap)
    pops += 1
    print("do:", name, "priority", priority)
print("pushes:", pushes, "pops:", pops)

Key points

  • Priority means an order of importance that decides what leaves first
  • Python's heapq module keeps a plain list arranged as a min-heap
  • A min-heap is a heap whose top value is the smallest value inside
  • Push and pop each cost log n steps, since values climb one tree level at a time
  • Peeking at the top costs one step, by reading index zero

In this example, each task enters the heap with a priority and a counter. The counter keeps equal priorities in arrival order. The heap list prints with the smallest priority at index zero. Pops then serve the urgent tasks first, and the two priority one tasks keep their arrival order. Four pushes and four pops drain the queue.

Note

heapq always builds a min-heap, so largest-first work stores negated values.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A heap built from [4, 1, 3] pops in which order?