Heaps and priority queues

A priority queue keeps many items and hands back the most important one next. The usual layout is a binary heap: an array read as a complete binary tree, where the children of index i sit at 2i+1 and 2i+2, so no pointers are stored. Each parent is at least as large as its children (a max-heap) or at most as large (a min-heap). Insert appends the item and swaps it up past smaller parents; removing the top moves the last item to the root and swaps it down. Both follow one root-to-leaf path, Θ(log n), and a heap can be built from n items in O(n). Heaps keep only that partial order, so finding an arbitrary item is still a linear scan.

Python’s heapq runs these algorithms on a plain list as a min-heap, with the smallest item at heap[0]. Java’s PriorityQueue gives O(log n) offer and poll, constant-time peek, and linear remove(Object) and contains. C++’s std::priority_queue returns the largest element by default, or the smallest with std::greater. Rust’s BinaryHeap is a max-heap whose push is O(1) expected for keys in random order and O(log n) amortized for ascending ones. Go’s container/heap works on any type implementing its interface, with Push and Pop in O(log n) and Init in O(n).

MIT’s 6.006 notes list typical uses: a router choosing which message to send next, an operating system scheduling processes, a discrete-event simulation finding the next event, and graph algorithms. Repeatedly popping a heap also sorts, which is heapsort.