What is a heap?

A heap is a binary tree that always keeps its smallest value at the top — or, in a max-heap, its largest. Reading that top value takes O(1). Adding a value or removing the top takes O(log n), however many values the heap holds.

That makes a heap the standard way to build a priority queue: a line where the most important item is served next, not the one that arrived first. Hospitals triage that way, operating systems schedule that way, and so do maps apps finding the shortest route.

Two rules make a heap

Walk up from any node and, in a min-heap, every step leads to a smaller or equal value. So the root is the smallest value in the whole tree — without the heap ever comparing it with the far-away nodes.