Stacks, Queues and Heaps: Three Restrictions That Buy You Speed

Stacks: last in, first out

Push and pop at one end only. Both are \(\Theta(1)\) amortised on a dynamic array, since they touch the end where appending is cheap.

The restriction is the point: LIFO is exactly the order in which nested things must be undone. Function calls unwind in reverse, which is why the call stack is a stack; matching brackets, undo history, and the iterative form of DFS are all the same shape.

def is_balanced(s):
    """Theta(n) time, Theta(n) worst-case space."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(is_balanced("a[b(c)d]{e}"))   # True
print(is_balanced("([)]"))          # False

In Python, use a plain list: append and pop() are the stack operations.

Queues: first in, first out

Enqueue at the back, dequeue at the front. FIFO processes things in arrival order, which is what you want for level-by-level exploration — BFS visits vertices in non-decreasing distance from the source precisely because its frontier is a queue — and for producer/consumer pipelines such as a data loader’s task queue.

Do not use a list as a queue. pop(0) shifts every remaining element and is \(\Theta(n)\), turning an \(O(V+E)\) BFS into \(O(V^2)\). Use collections.deque, a double-ended queue implemented as a doubly linked list of fixed-size blocks: append, appendleft, pop and popleft are all \(\Theta(1)\) worst case, at the price of \(\Theta(n)\) indexing in the middle.

A deque subsumes both structures — and gives you sliding-window maxima, monotonic queues, and ring buffers via deque(maxlen=k).

Heaps: a tree with no pointers

A binary heap is a complete binary tree — every level full except possibly the last, which fills left to right — satisfying the heap property: every node is \(\le\) both of its children (min-heap). Completeness means it can be stored in an array with no pointers at all:

Push appends at the end and sifts up: swap with the parent while it is smaller. Pop-min returns index 0, moves the last element to the root and sifts down: swap with the smaller child while it is larger. Both walk one root-to-leaf path, so both are \(\Theta(\log n)\) worst case. Reading the minimum is \(\Theta(1)\).

Why build-heap is Θ(n)

Heapifying an arbitrary array by pushing \(n\) items one at a time costs \(O(n \log n)\). Doing it bottom-up — sift down every node from the last internal node backwards — costs only \(\Theta(n)\).

The argument is a counting one. In a heap of \(n\) nodes there are at most \(\lceil n/2^{h+1}\rceil\) nodes of height \(h\), and sifting a node of height \(h\) costs \(O(h)\). So the total is

using \(\sum_{h\ge0} h/2^h = 2\). The intuition the sum formalises: half the nodes are leaves and move zero steps, a quarter move at most one, an eighth at most two. The expensive nodes are the rare ones. Only the root can travel the full \(\log_2 n\).

Priority queues

A priority queue serves the smallest key next, and a heap is its standard implementation: \(\Theta(\log n)\) insert and extract-min worst case, \(\Theta(1)\) peek. This is what Dijkstra runs on, what schedulers use, and how you keep the top \(k\) of a stream in \(\Theta(n \log k)\) time and \(\Theta(k)\) space.

import heapq

def top_k(stream, k):
    """k largest items, Theta(n log k) time, Theta(k) space."""
    heap = []                      # a MIN-heap of the k largest so far
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:          # heap[0] is the smallest kept item
            heapq.heapreplace(heap, x)   # pop the smallest, push x
    return sorted(heap, reverse=True)

print(top_k([5, 1, 9, 3, 7, 2], 3))   # [9, 7, 5]

data = [5, 1, 9, 3, 7, 2]
heapq.heapify(data)                    # Theta(n), in place
print(data[0])                         # 1  -- the minimum
print(data)                            # a valid heap, NOT a sorted list

heapq gives a min-heap only; for a max-heap, push negated keys. It has no decrease-key, so the usual pattern is to push a new entry and skip stale ones when popped (“lazy deletion”).

References

1. Williams, J. W. J. Algorithm 232: Heapsort. Communications of the ACM 7(6), 347–348, 1964.
2. Floyd, R. W. Algorithm 245: Treesort 3. Communications of the ACM 7(12), 701, 1964 — the linear bottom-up construction.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 4th ed. MIT Press, 2022 — ch. 6.
4. Python Software Foundation. heapq — Heap queue algorithm and collections.deque.
5. CPython source. Modules/_collectionsmodule.c — the block-linked-list deque.