Heapq for Priority Queues

Introduction

Heapq implements min-heap priority queues, essential for efficient sorting and scheduling.

Basic Heap Operations

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)

print(heap[0])       # Smallest: 2
heapq.heappop(heap)  # Remove and return: 2

# From list
heapq.heapify([5, 2, 8, 1])  # Converts to valid heap

Heap Sort

import heapq

def heap_sort(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

print(heap_sort([5, 2, 8, 1, 9]))  # [1, 2, 5, 8, 9]

Max Heap Trick

# Python heaps are min-heaps
# Negate values for max behavior

heap = []
heapq.heappush(heap, -10)  # Store negative
heapq.heappush(heap, -5)

print(-heap[0])  # 10 (maximum)

Practice Problems

1. Implement task scheduler with priorities
2. Find K largest elements using heap
3. Merge sorted lists efficiently
4. Implement median maintenance
5. Create Huffman coding with heap