09Module · Goodrich Ch. 9

Week 9 — Priority Queues & Heaps

Heap data structure, bottom-up construction, heap-sort, and adaptable priority queues with locators.

The priority-queue ADT, array-based complete binary trees, heap-sort, and Python's heapq module.

Theory

A priority queue returns the minimum (or maximum) element on demand. Min-heap is the standard array-based implementation.

Heap operations: insert and extract-min each run in O(log n); peek-min is O(1).

Bottom-up heap construction (heapify) builds a heap from an unordered array in O(n) — not O(n log n).

Heap-sort sorts in O(n log n) in place by repeatedly extracting the root into the tail of the array.

Key points

Parent of index i is (i-1)//2; children are 2i+1 and 2i+2.
Use heapq.heappush / heappop; Python's heapq is a min-heap (push negatives for max-heap behavior).
Adaptable priority queues store locators so you can change-key in O(log n).

Code examples

Heap-sort with heapq

import heapq

def heap_sort(a):
    h = list(a)
    heapq.heapify(h)              # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heap_sort([3, 1, 4, 1, 5, 9, 2, 6]))

K smallest with a max-heap of size k

import heapq

def k_smallest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, -x)
        if len(h) > k:
            heapq.heappop(h)
    return sorted(-y for y in h)