Priority Queue: heapq - Introduction to Programming - Python

Priority Queue: heapq

Min-heap operations using Python's heapq module — push, pop, heapify, the negation trick for max-heap, and practical CP examples.

How a Heap Works

A heap is a binary tree stored as a list where every parent is smaller than its children. The smallest element is always at index 0:

Stored as: [1, 3, 5, 4, 8, 7, 9]

You never need to manage the tree structure manually — heapq handles it entirely through the list.

Python's heapq module implements a min-heap: the smallest element is always at the top and can be retrieved in O(1). Insertion and removal are O(log n).

Basic Operations

Operation	Code	Complexity
Push	`heappush(h, x)`	O(log n)
Pop minimum	`heappop(h)`	O(log n)
Peek minimum	`h[0]`	O(1)
Build heap from list	`heapify(lst)`	O(n)
Size	`len(h)`	O(1)

`heapify` — Build a Heap from a List

If you already have a list, convert it to a heap in place with — much faster than pushing elements one by one:

Up next

Problems

part 1

heapify

Feature	`heapq`
Type	Min-heap
Push	`heappush(h, x)` — O(log n)
Pop min	`heappop(h)` — O(log n)
Peek min	`h[0]` — O(1)
Build from list	`heapify(lst)` — O(n)
Max-heap	Negate values
Top K smallest	`nsmallest(k, a)`
Top K largest	`nlargest(k, a)`

import heapq

h = []

heapq.heappush(h, 5)    # push
heapq.heappush(h, 2)
heapq.heappush(h, 8)
heapq.heappush(h, 1)

print(h[0])                  # peek — smallest element: 1
print(heapq.heappop(h))      # pop minimum: 1
print(heapq.heappop(h))      # pop minimum: 2
print(h)                     # [5, 8] — heap maintained automatically

import heapq

tasks = []
heapq.heappush(tasks, (3, "low priority task"))
heapq.heappush(tasks, (1, "urgent task"))
heapq.heappush(tasks, (2, "normal task"))

while tasks:
    priority, task = heapq.heappop(tasks)
    print(priority, task)
# 1 urgent task
# 2 normal task
# 3 low priority task

import heapq

lower = []   # max-heap (negated)
upper = []   # min-heap

def add(x):
    heapq.heappush(lower, -x)

    # Balance: move top of lower to upper if needed
    if upper and -lower[0] > upper[0]:
        heapq.heappush(upper, -heapq.heappop(lower))

    # Keep sizes balanced
    if len(lower) < len(upper):
        heapq.heappush(lower, -heapq.heappop(upper))
    elif len(lower) > len(upper) + 1:
        heapq.heappush(upper, -heapq.heappop(lower))

def median():
    if len(lower) > len(upper):
        return -lower[0]
    return (-lower[0] + upper[0]) / 2

n = int(input())
for _ in range(n):
    x = int(input())
    add(x)
    print(median())

Priority Queue: heapq

How a Heap Works

Basic Operations

`heapify` — Build a Heap from a List

Max-Heap: The Negation Trick

`nlargest` and `nsmallest`

Heaps with Tuples

Practical CP Examples

K-th Smallest Element

K-th Largest Element

Running Median (Two Heaps)

Merge K Sorted Lists

Summary

Priority Queue: heapq

How a Heap Works

Basic Operations

heapify — Build a Heap from a List

Max-Heap: The Negation Trick

nlargest and nsmallest

Heaps with Tuples

Practical CP Examples

K-th Smallest Element

K-th Largest Element

Running Median (Two Heaps)

Merge K Sorted Lists

Summary

`heapify` — Build a Heap from a List

`nlargest` and `nsmallest`