Some programs do not need to process items in the order they arrived. A hospital triage system, a task scheduler, and a route planner may instead need the most urgent or lowest-cost item next. A priority queue exposes that item; a heap is a compact structure commonly used to implement it.
The heap rule
A binary min-heap is a complete binary tree in which every parent is less than or equal to its children. The root is therefore the smallest value. A max-heap reverses the comparison so the largest value is at the root. A heap is not fully sorted: it only guarantees the parent-child ordering needed to find the next priority quickly.
Store the tree in an array
Because a heap is complete, its nodes fit neatly in an array without storing pointers. With zero-based indexing, a node at index i has children at 2i + 1 and 2i + 2; its parent is at floor((i - 1) / 2). This layout is compact and works well with CPU caches.
def push(heap, value):
heap.append(value)
child = len(heap) - 1
while child > 0:
parent = (child - 1) // 2
if heap[parent] <= heap[child]:
break
heap[parent], heap[child] = heap[child], heap[parent]
child = parentWhy the operations are efficient
- Peek: read the root in
O(1). - Insert: append a value, then sift it toward the root in
O(log n). - Remove the minimum: move the last item to the root, then sift it down in
O(log n). - Build from many values: bottom-up heap construction takes
O(n), notO(n log n).
Heaps are useful when the next best item matters repeatedly but the entire collection does not need sorting. They power event queues, job schedulers, and Dijkstra's shortest-path algorithm. If you need fast lookup by an arbitrary key as well, a heap alone is not enough.