Priority Queue: heapq - Язык программирования Python для спортивного программирования

Priority Queue: heapq

Learn priority queue in python

Priority Queue: `heapq`

A priority queue is a data structure where each element has a priority, and the element with the highest (or lowest) priority is always served first — regardless of insertion order.

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).

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.

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

Up next

Problems

part 1

len(h)

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)`
C++ equivalent	`std::priority_queue` (max by default)

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