Suppose tasks arrive with different priorities, and the next task must always be the most urgent one. A priority queue provides that behavior; a heap implements it with an array and rules that keep the highest-priority task at the root. Unlike a sorted array, the heap does not keep every item in order. section 2.4 section 2.5.3
Think of a binary heap as a complete, left-adjusted binary tree: each node has at most two children, and the last level fills from left to right. Every node has priority at least as high as any node below it. These rules make the root easy to find while allowing the tree to fit compactly in an array, without parent or child pointers. With zero-based indexing, the children of index i are at 2i+1 and 2i+2; its parent is at floor((i−1)/2). section 2.5.3
Figure 2.4 A binary heap. Only priorities are shown for the nodes (elements are irrelevant here).The numbers inside the small squares show the indices of the heap elements in the array. Nodes are matched into array elements top to bottom, left to right. Top: the tree representation for the heap. Notice how every parent is smaller than (or at most equal to) its children and, in turn, all elements in its subtree. Bottom: the same heap in its array representation.
The paired tree and array views show how level-order positions encode parent–child relationships. section 2.5.3
“Highest priority” depends on the chosen ordering. A max-heap puts larger priorities at the root; a min-heap puts smaller ones there. A general-purpose implementation can use a priority function, while a specialized one may store priority–task pairs directly. section 2.5.4
Changes to the array may break the priority rule, so operations repair it along a path through the tree:
- Insert adds an item and bubbles it toward the root until its parent has sufficient priority. It takes O(log n) time. section 2.6 section 2.6.9
- Peek reads the root in O(1). Top removes and returns it, moves the last array item to the root, then pushes that item down to a valid position in O(log n). section 2.6.4 section 2.6.9
- Heapify builds from an existing array: treat leaves as valid heaps, then push down each internal node from right to left. This takes O(n), rather than the O(n log n) upper bound for repeated insertion. section 2.6.7 section 2.6.9
A heap is not a search structure. Finding an arbitrary element takes O(n); an auxiliary map from elements to array positions can support average O(1) lookup and efficient priority updates, at O(n) extra space. Dynamic-array resizing also means logarithmic insert and top bounds are amortized rather than guarantees for every individual call. section 2.6.8 section 2.6.9
Heaps help when processing order matters: an auxiliary heap can find the k largest items using O(n+k log k) work and O(k) extra memory, while Dijkstra’s algorithm uses a min-heap to prioritize discovered vertices by distance. A binary heap is often enough, but a d-ary heap can reduce tree height at the cost of comparing more children during push-down; profiling determines whether that trade-off helps. section 2.7 section 14.4.3 section 2.9.2
