Heap

Keep the single most extreme element instantly readable at the root of a partially ordered tree, so insert and extract cost only O(log n) under continuous churn by declining to maintain any more order than the extreme requires.

Version

v4 · 2026-09-28 · History · 2 corrections

Domain-specific #

496

Domain group

Applied Sciences & Engineering

Origin domain

Computer Science & Software Engineering

Subdomain

Data Structures and Algorithms → Computer Science & Software Engineering

Core Idea

A heap is a tree-structured data structure satisfying the heap property: every node is at least as extreme in priority as its children, so the global maximum or minimum always sits at the root and is readable in O(1). Insertion and root-extraction restore the property by sifting an element up or down the tree, each in O(log n). The canonical binary heap stores this implicit tree in a contiguous, pointer-free array.

How would you explain it like I'm…

Biggest-On-Top Tree

Imagine a family tree of toys where every parent toy is bigger than the toys below it. Then the biggest toy is always at the very top, so you can grab it right away. When you add or take away a toy, you swap toys up or down until every parent is bigger again.

The Boss-At-The-Top Tree

A Heap is a way computers organize things in a tree shape, where each item has a parent above it and children below it. The rule is that every parent is at least as big as its children (or at least as small, for the other kind). Because of that rule, the biggest (or smallest) item always sits at the top. When you add a new item, it goes in the next open spot and swaps upward with its parent until the rule is true again. When you remove the top, the last item moves to the top and swaps downward until things are fixed.

Parent-Beats-Child Priority Tree

A Heap is a tree-shaped data structure obeying the heap property: in a max-heap every node's key is greater than or equal to its children's, and in a min-heap it's less than or equal. This guarantees the most extreme element is at the root, so you can look at it instantly. Inserting places the new element at the next open position and 'sifts it up' by swapping with its parent; removing the root moves the last element to the top and 'sifts it down'. Because the tree stays complete and balanced, these fixes take only about log n steps. Unlike a fully sorted list, a heap only promises that the top is extreme, not that everything is in order. Heaps are the usual way to build a priority queue, which always hands you the most urgent item next.

 

A heap is a tree satisfying the heap property: each node's key is at least as extreme as its children's (≥ for a max-heap, ≤ for a min-heap), so the global extreme sits at the root and is readable in O(1). The binary heap is a complete binary tree, so its height is ⌊log₂ n⌋, and both insertion (place at the next open position, sift up) and root extraction (move the last element to the root, sift down by swapping with the more extreme child) run in O(log n). It is usually stored implicitly in an array: node i has parent ⌊(i−1)/2⌋ and children 2i+1 and 2i+2, so no pointers are needed and memory is contiguous and cache-friendly. The heap implements the priority queue ADT with insert and extract-extreme. Dijkstra's algorithm, Prim's algorithm and A* rely on efficient extract-min, making their inner loop O(log n) instead of O(n) for a linear scan. Variants include d-ary heaps (shallower trees, more comparisons per sift-down), Fibonacci heaps (amortised O(1) decrease-key, giving O(E + V log V) Dijkstra but high constants), and pairing heaps (similar amortised bounds, simpler). In practice the array binary heap is the default.

Scope of Application

The heap lives across the algorithm and systems subfields of software wherever the inner loop is "pull the most urgent open item while items keep arriving," bounded by the precondition of contiguous memory and integer indexing.

• Graph algorithms — the frontier of Dijkstra, Prim, and A*, turning an O(n²) loop into O(n log n).
• Discrete-event simulation — the future-event list keyed by event time.
• Operating systems — priority schedulers and timer / retry-backoff structures.
• Streaming statistics — the two-heap construction maintaining a running median.

Clarity

The heap makes legible the amortised cost of repeated extreme-access under churn, reducing an O(n) scan to O(log n) per operation. It sharpens the distinction that the heap maintains cheap access to the extreme, not a sorted order — the second maximum still costs an extract-then-reheapify — framing the design as a budget over insert, extract-extreme, and decrease-key.

Manages Complexity

Many algorithms reduce to the same inner-loop demand, and the heap collapses them to one structure with one cost profile: O(1) at the root, O(log n) per mutation. The deeper compression is in what it declines to track — only partial order — which fixes the controlling branch (one extreme, or the whole ordering?) and reduces variant choice to a three-operation budget.

Abstract Reasoning

The heap licenses cost prediction via the heap property, boundary-drawing on how much order it maintains (fast precisely because it refuses to sort), and interventionist variant selection by reading off which of insert, extract-extreme, or decrease-key dominates. It also bounds itself against the priority-queue ADT and the substrate-independent act of prioritizing.

Knowledge Transfer

Within software the heap transfers as mechanism wherever the inner loop pulls the most urgent item, the whole apparatus carrying intact across graph algorithms, simulation, schedulers, and streaming statistics. Beyond software the portable thing is the parent prime Prioritization (realized as the priority-queue ADT), which genuinely recurs in triage and dockets. But the sift machinery and index arithmetic presuppose random-access memory; "triage is a heap" is analogy, not mechanism transfer.

Relationships to Other Abstractions

Current abstraction Heap Domain-specific

Parents (2) — outgoing typed relations

• Heap is a kind of Data Structure Prime

  A heap is a data structure specialized to a partial-order invariant that keeps one extreme cheap under continuous insertion and extraction.

• Heap is a decomposition of Prioritization Prime

  Removing heap representation machinery leaves prioritization's discipline of keeping the most urgent open item available under continuing churn.

Hierarchy paths (4) — routes to 3 parentless roots

• Heap → is a kind of Data Structure → presupposes, typical Trade-offs → presupposes Constraint

Show alternative paths (3)

Neighborhood in Abstraction Space

Heap sits in a sparse region of the domain-specific corpus (73^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Storage & Lookup Data Structures (21 abstractions)

Nearest neighbors

• Fragmentation (computing) — 0.84
• Heapsort — 0.83
• Nested Set Model — 0.83
• Bloom Filter — 0.83
• Programming Fold — 0.83

Computed from structural-signature embeddings · 2026-10-25