Heaps

Concepts

• A heap is a complete binary tree that satisfies a heap order. It is a binary tree, not a binary search tree: siblings are not ordered relative to each other.
• Order property:
  • Min heap: every node is smaller than or equal to its children, so the root is the minimum. This holds recursively for every subtree.
  • Max heap: the reverse; the root is the maximum.
• Structure property: all levels are completely filled except possibly the last, and the last level is filled from the left.
• Because it is complete, the tree is stored in an array with no pointers.

Array indexing

Operations

Edge cases in pop: an empty heap returns nothing, a heap with one element just removes the root, and during sift down a node may have two children, only a left child, or none.

See Push and Pop and Heapify.

Priority queue

• A priority queue serves elements by priority instead of insertion order. A binary heap is the standard implementation.

• Uses: Dijkstra’s and Prim’s algorithms, Huffman coding, scheduling, merging k sorted lists, running median, top-K problems.
• Python’s heapq is a min heap only. For a max heap, push negated values. For tuples such as (priority, item), ties compare the next field, so use a tie-breaking counter if items are not comparable.

Recognition signals

• “k-th largest or smallest”, “top K”, “k most frequent”, “k closest”: top-K pattern.
• “Repeatedly take the smallest or largest, then put something back” (last stone weight, task scheduling).
• “Merge k sorted lists or arrays”.
• “Median of a stream”: two heaps.
• Shortest path or MST with weights: Dijkstra’s, Prim’s.

Top K elements

• To find the K largest, keep a min heap of size K: push each element and pop when the size exceeds K. The root is then the K-th largest, in $O(n \log K)$ time and $O(K)$ space. For the K smallest, use a max heap.
• Alternatives: sort in $O(n \log n)$, or quickselect in $O(n)$ average time.
• If all data is already in memory and you can afford $O(n)$ extra work, heapify the whole array and pop K times: $O(n + K \log n)$.
• For streams, keep the size-K heap alive and update it per element (Kth Largest Element in a Stream).

Two heaps

Used for a running median or for splitting data into a smaller half and a larger half.

• Keep a max heap small for the lower half and a min heap large for the upper half.
• Invariants: every element of small is less than or equal to every element of large, and their sizes differ by at most one.
• Add a value to small, move the top of small to large, and if large is bigger, move its top back to small.
• Median: the top of the larger heap, or the average of both tops when sizes are equal. Each add is $O(\log n)$; reading the median is $O(1)$.

import heapq
 
class MedianFinder:
    def __init__(self):
        self.small = []  # max heap (negated values)
        self.large = []  # min heap
 
    def addNum(self, num):
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))
 
    def findMedian(self):
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

Templates

• Push and Pop: heap implementation with push (sift up) and pop (sift down).
• Heapify: building a heap from an array in $O(n)$.

Problems