What Is a Heap? - Learning Module

Loading content...

0/276

The Heap Property — Max-Heap vs Min-Heap

The Ordering That Enables Everything

The heap property is deceptively simple: every parent dominates its children. Yet this single invariant unlocks a remarkable ability—instant access to the extreme element (minimum or maximum) of an entire collection, maintained efficiently as elements are added and removed.

In this page, we'll dissect the heap property with surgical precision. We'll understand exactly what 'dominates' means, why max-heaps and min-heaps are fundamentally the same structure with inverted comparison, how the property propagates through the tree, and the profound consequences for algorithm design. By the end, you'll have complete mastery over this foundational invariant.

What You Will Learn

By the end of this page, you will: (1) State the exact formal definitions of max-heap and min-heap properties, (2) Prove that the root contains the extreme element, (3) Understand why sibling ordering is undefined and what that implies, (4) Analyze the consequences for searching and iteration, (5) Know when to choose max-heap vs min-heap for specific problems.

The Max-Heap Property — Formal Definition

Let's establish the max-heap property with mathematical rigor:

Definition (Max-Heap Property): A binary tree satisfies the max-heap property if and only if, for every node N in the tree:

value(N) ≥ value(C) for every child C of N

Equivalently, by transitivity:

For every node N and every descendant D of N: value(N) ≥ value(D)

Deconstructing the Definition:

1. 'For every node N': The property must hold at EVERY internal node—not just the root, not just some nodes—every single node with children. This universality is what makes the property an invariant.

2. 'value(N) ≥ value(C)': The inequality is non-strict. Equal values are permitted. This is crucial for handling duplicates.

3. 'for every child C': Both children (if present) must satisfy the relationship. The left child AND the right child must each be ≤ the parent.

4. Transitivity Extension: While we state the property in terms of parent-child pairs, it implies that any ancestor is ≥ any descendant. The root, being an ancestor of all nodes, is thus ≥ every element in the heap.

The Root Theorem for Max-Heaps

Theorem: In a non-empty max-heap, the root contains the maximum element.

Proof: Let r be the root value. For any other node n, there exists a path from r to n through ancestors. By the max-heap property at each step: r ≥ value(parent of n) ≥ ... ≥ value(n). Thus r ≥ value(n) for all n. Therefore r is maximum. ∎

Visualizing the Max-Heap Property:

Consider this valid max-heap:

           100
          /   \
        90     80
       /  \   /  \
      85  75 70  60
     /
    50

Verify the property at each internal node:

Node 100: 100 ≥ 90 ✓ and 100 ≥ 80 ✓
Node 90: 90 ≥ 85 ✓ and 90 ≥ 75 ✓
Node 80: 80 ≥ 70 ✓ and 80 ≥ 60 ✓
Node 85: 85 ≥ 50 ✓

Notice: 85 > 80, but 85 is at a lower level than 80. This is fine! The heap property doesn't require elements at the same level to follow any order, nor does it require all elements at level k to be larger than all elements at level k+1. Only the ancestor-descendant relationship matters.

The Min-Heap Property — Mirror Image

The min-heap property is the exact mirror of the max-heap property:

Definition (Min-Heap Property): A binary tree satisfies the min-heap property if and only if, for every node N in the tree:

value(N) ≤ value(C) for every child C of N

Equivalently:

For every node N and every descendant D of N: value(N) ≤ value(D)

The Root Theorem for Min-Heaps

Theorem: In a non-empty min-heap, the root contains the minimum element.

Proof: Analogous to the max-heap proof, with inequalities reversed. By transitivity of ≤ along any ancestor-descendant path, the root value is ≤ every other value. ∎

Visualizing the Min-Heap Property:

            5
          /   \
        10     15
       /  \   /  \
      20  25 30  35
     /
    40

Verify the property at each internal node:

Node 5: 5 ≤ 10 ✓ and 5 ≤ 15 ✓
Node 10: 10 ≤ 20 ✓ and 10 ≤ 25 ✓
Node 15: 15 ≤ 30 ✓ and 15 ≤ 35 ✓
Node 20: 20 ≤ 40 ✓

The minimum (5) floats to the top, exactly as expected.

Max-Heap vs Min-Heap Comparison
Property	Max-Heap	Min-Heap
Ordering	Parent ≥ Children	Parent ≤ Children
Root Contains	Maximum element	Minimum element
Path to Root	Values increase going up	Values decrease going up
Leaves	May contain any values	May contain any values
Extract Returns	Largest element	Smallest element
Common Use Case	Max priority queue	Min priority queue

The Duality Principle — One Structure, Two Views

Here's a profound insight that simplifies your mental model:

Duality Principle: Max-heaps and min-heaps are not two different data structures—they are the same data structure with inverted comparison operations.

Proof by Construction:

Given any max-heap storing values {v₁, v₂, ..., vₙ}, if we negate every value to get {-v₁, -v₂, ..., -vₙ}, the result is a valid min-heap with identical structure.

Why? If parent P ≥ child C in the original, then (-P) ≤ (-C) in the negated version.

Conversely, any min-heap becomes a max-heap when all values are negated.

Practical Implication

If your programming language provides only a min-heap (like Python's heapq), you can simulate a max-heap by inserting negated values and negating again on extraction. This is a standard technique: to get the maximum from a min-heap of n values, insert -v for each value v, then return -(extract_min()).

Implementation Abstraction:

In well-designed heap implementations, max-heap vs min-heap is controlled by a comparator function, not by code duplication:

// Pseudocode for a configurable heap
class Heap:
    comparator  // function(a, b) → boolean
    
    // For max-heap: comparator = (a, b) → a > b
    // For min-heap: comparator = (a, b) → a < b
    
    function parent_dominates(parent, child):
        return comparator(parent, child) or parent == child

This abstraction means:

All heap algorithms use identical logic—only the comparison differs
You can create heaps ordered by any criterion (min by age, max by priority, etc.)
Understanding one is understanding both

The Comparison Function Pattern

Many heap implementations accept a custom comparator. For objects with multiple fields, you can create a max-heap by priority but a min-heap by timestamp, or any combination. The heap doesn't care about the semantics—it just calls the comparator. This is powerful for complex priority queue applications.

What the Heap Property Does NOT Guarantee

Understanding what the heap property does NOT provide is as important as understanding what it does. This clarifies the heap's role and prevents incorrect usage.

The Heap Property Does NOT Provide

•No sibling ordering — The left child could be larger or smaller than the right child. In fact, because of how insertion works, 'older' elements that should be larger might end up as right children of 'newer' smaller elements.
•No level ordering — Elements at level k are NOT guaranteed to all be larger than elements at level k+1. The heap 100→90,80→85,75,70,60 has 85 at level 3 but 80 at level 2, and 85 > 80.
•No uniqueness of structure — Many valid heap arrangements exist for the same set of values. The specific arrangement depends on insertion order.
•No efficient arbitrary search — Finding whether 42 exists in the heap is O(n)—you might need to inspect every node. There's no binary search property.
•No efficient k-th element access — Finding the 5th largest element in a max-heap requires removing 5 elements. It's not a positional structure.
•No sorted iteration — Traversing a heap (preorder, inorder, etc.) does NOT give sorted order. To get sorted output, you must repeatedly extract.

The Search Trap

A common mistake is attempting binary search on a heap because it's a binary tree. This fails completely. In a BST, left < parent < right enables binary search. In a heap, left and right have NO ordering relationship with each other. You cannot eliminate half the tree at any step except when the target is larger (max-heap) or smaller (min-heap) than a node, letting you skip that subtree.

The Second-Largest Element Problem:

Where is the second-largest element in a max-heap? Surprisingly, we only know it's one of the root's children.

Why? The second-largest must have lost a comparison only to the maximum. Since the maximum is at the root, and the only elements that ever compared directly to the root during insertion are its two children, the second-largest is either the left or right child of the root.

For the third-largest, the situation is worse—it could be among the top 3 levels (root's children or grandchildren). For general k-th largest, the problem expands to examining the top ⌈log₂(k)⌉ levels.

This demonstrates that heaps provide efficient access to exactly one extreme, not to ranking in general.

The Locality Property — Subtrees as Independent Heaps

One of the most elegant properties of heaps—and one that enables elegant recursive algorithms—is that every subtree is itself a valid heap.

Locality Theorem: If a binary tree satisfies the heap property, then the subtree rooted at any node also satisfies the heap property.

Proof: Let T be a heap and let S be the subtree rooted at node N. For any node M in S with child C, both M and C are in T (since S ⊆ T). Since T is a heap, value(M) ≥ value(C) (max-heap case). Since this holds for all parent-child pairs in S, S is a heap. ∎

Why Locality Matters

The locality property is crucial for heap operations. When we insert or delete, we only need to restore the heap property along ONE path from the modified position to the root (or to a leaf). The rest of the heap remains valid. This is why operations are O(log n)—we fix at most O(height) violations, and height = O(log n) for a complete tree.

The Inductive Power of Locality:

Locality enables reasoning about heaps inductively:

Base Case: A single node (no children) trivially satisfies the heap property.

Inductive Case: If both subtrees of a node are valid heaps, and the node dominates its immediate children, then the entire tree rooted at that node is a valid heap.

This inductive structure powers:

Heapify Down: Given a node whose children are heap roots, make it a heap root too
Build Heap: Work bottom-up—leaves are already heaps, then fix progressively upward
Prove Correctness: Reason about operations by induction on tree height

Visualizing Subtree Heaps:

           100           <- root of full heap
          /   \
        90     80        <- each is root of a sub-heap
       /  \   /  \
      85  75 70  60      <- each is root of its sub-heap
     /
    50                   <- a one-node heap is trivially valid

Each encircled portion is independently a valid heap:

The subtree rooted at 90 (containing 90, 85, 75, 50) is a max-heap
The subtree rooted at 80 (containing 80, 70, 60) is a max-heap
The subtree rooted at 85 (containing 85, 50) is a max-heap
Every single-node 'subtree' is a max-heap

This recursive structure is what makes heaps 'work'—operations manipulate small portions while leaving the rest provably intact.

Heap Property Violations and Restoration

When does the heap property get violated, and how do we restore it? Understanding this prepares you for the insert and extract operations.

How Violations Occur

•Insertion: New element at the bottom might be larger than its parent (in max-heap), violating the property upward
•Extraction: After removing root and moving last element to root, the new root might be smaller than its children, violating downward
•Decrease-key: Decreasing a value might make it smaller than its children (max-heap), violating downward
•Increase-key: Increasing a value might make it larger than its parent (max-heap), violating upward

How Violations Are Fixed

•Bubble Up (Heapify Up): Swap node with parent repeatedly until parent dominates or root is reached
•Bubble Down (Heapify Down): Swap node with dominating child repeatedly until node dominates children or is a leaf
•Key insight: Only ONE direction of violation can occur at a time—a node can't simultaneously be > parent AND < children

The Single-Path Repair Property

A crucial observation: after any single modification (insert, delete, key change), the heap property is violated along at most ONE root-to-leaf path. Restoration involves fixing nodes along this single path, giving O(log n) time. The rest of the heap remains untouched and valid.

The Bubble Up Algorithm (Preview):

function bubble_up(heap, index):
    while index > 0:
        parent_idx = (index - 1) // 2
        if heap[parent_idx] >= heap[index]:  // Max-heap: parent dominates
            break  // No violation
        swap(heap[parent_idx], heap[index])  // Fix violation
        index = parent_idx  // Move up

The Bubble Down Algorithm (Preview):

function bubble_down(heap, index, heap_size):
    while true:
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < heap_size and heap[left] > heap[largest]:
            largest = left
        if right < heap_size and heap[right] > heap[largest]:
            largest = right
            
        if largest == index:
            break  // No violation
        
        swap(heap[index], heap[largest])
        index = largest  // Move down

We'll explore these in detail in the operations module. For now, observe how the heap property's local nature enables simple, efficient restoration.

Choosing Between Max-Heap and Min-Heap

When solving problems, how do you decide between max-heap and min-heap? The choice relates directly to which extreme you need to access efficiently.

Problem Patterns and Heap Selection
Problem Type	Heap Choice	Reasoning
Find k largest elements	Min-heap of size k	Min-heap gives smallest of the k largest; if new element > min, replace
Find k smallest elements	Max-heap of size k	Max-heap gives largest of the k smallest; if new element < max, replace
Merge k sorted lists	Min-heap of k elements	Always extract the overall minimum from current heads
Task scheduling (earliest deadline)	Min-heap by deadline	Always process task with soonest deadline
Task scheduling (highest priority first)	Max-heap by priority	Always process task with highest priority
Dijkstra's shortest path	Min-heap by distance	Always expand node with minimum tentative distance
Huffman coding	Min-heap by frequency	Always combine two least frequent symbols
Running median	Max-heap + Min-heap	Max-heap for lower half, min-heap for upper half

The Counter-Intuitive k-Largest Pattern

Finding the k largest elements uses a MIN-heap, not a max-heap. Why? You maintain a heap of size k. When a new element arrives: if it's larger than the minimum (heap root), it deserves to be in the top k—so remove the minimum and insert the new element. The min-heap lets you efficiently identify and remove the 'worst' of your current candidates.

The Decision Framework:

Ask yourself: Which element do I need to find or remove most often?

If you need the maximum frequently → Max-Heap
If you need the minimum frequently → Min-Heap

Then ask: Am I tracking a 'best k' set where I need to evict the worst candidate?

If tracking k largest and evicting the smallest of them → Min-heap of size k
If tracking k smallest and evicting the largest of them → Max-heap of size k

This second pattern (k-tracking) is counterintuitive but extremely common. The heap contains your candidates, and its root is the element you're most willing to evict—making it easy to compare against newcomers.

Language Default Matters

Different languages have different defaults. Python's heapq is a min-heap. Java's PriorityQueue is a min-heap by default. C++'s priority_queue is a max-heap by default. Know your language's default and how to switch (usually via a comparator or negation trick).

Summary: Mastering the Heap Property

We've explored the heap property in depth—the ordering invariant that gives heaps their power. Let's consolidate the key insights:

Key Takeaways

•Max-heap: Every parent ≥ its children; root is maximum. Min-heap: Every parent ≤ its children; root is minimum.
•Transitivity: The property extends to all ancestor-descendant pairs—the root dominates the entire heap.
•Duality: Max-heap and min-heap are the same structure with inverted comparison. Understanding one means understanding both.
•No sibling ordering: Left and right children have no required relationship. This is NOT a search tree.
•Locality: Every subtree is a valid heap. Operations affect only a single path.
•Single-path repair: Violations are fixed by bubbling up or down along one path—O(log n) time.
•Problem mapping: Choose max-heap to access maximum, min-heap to access minimum. For k-element tracking, use the 'opposite' heap.

What's next:

With the heap property understood, we now turn to the equally important shape property—the complete binary tree structure. This structural requirement is what enables the array-based representation that makes heaps so memory-efficient and cache-friendly. It's also what guarantees O(log n) height, which in turn guarantees O(log n) operations.

Page Complete

You now have complete mastery of the heap property—both max-heap and min-heap variants. You understand what it guarantees (root is extreme, transitivity holds, subtrees are heaps) and what it doesn't (no sibling order, no efficient search). Next, we explore the shape property that completes the heap definition.

The Heap Property — Max-Heap vs Min-Heap

The Ordering That Enables Everything

What You Will Learn

The Max-Heap Property — Formal Definition

Let's establish the max-heap property with mathematical rigor:

Definition (Max-Heap Property): A binary tree satisfies the max-heap property if and only if, for every node N in the tree:

value(N) ≥ value(C) for every child C of N

Equivalently, by transitivity:

For every node N and every descendant D of N: value(N) ≥ value(D)

Deconstructing the Definition:

2. 'value(N) ≥ value(C)': The inequality is non-strict. Equal values are permitted. This is crucial for handling duplicates.

3. 'for every child C': Both children (if present) must satisfy the relationship. The left child AND the right child must each be ≤ the parent.

The Root Theorem for Max-Heaps

Theorem: In a non-empty max-heap, the root contains the maximum element.

Visualizing the Max-Heap Property:

Consider this valid max-heap:

           100
          /   \
        90     80
       /  \   /  \
      85  75 70  60
     /
    50

Verify the property at each internal node:

Node 100: 100 ≥ 90 ✓ and 100 ≥ 80 ✓
Node 90: 90 ≥ 85 ✓ and 90 ≥ 75 ✓
Node 80: 80 ≥ 70 ✓ and 80 ≥ 60 ✓
Node 85: 85 ≥ 50 ✓

The Min-Heap Property — Mirror Image

The min-heap property is the exact mirror of the max-heap property:

Definition (Min-Heap Property): A binary tree satisfies the min-heap property if and only if, for every node N in the tree:

value(N) ≤ value(C) for every child C of N

Equivalently:

For every node N and every descendant D of N: value(N) ≤ value(D)

The Root Theorem for Min-Heaps

Theorem: In a non-empty min-heap, the root contains the minimum element.

Proof: Analogous to the max-heap proof, with inequalities reversed. By transitivity of ≤ along any ancestor-descendant path, the root value is ≤ every other value. ∎

Visualizing the Min-Heap Property:

            5
          /   \
        10     15
       /  \   /  \
      20  25 30  35
     /
    40

Verify the property at each internal node:

Node 5: 5 ≤ 10 ✓ and 5 ≤ 15 ✓
Node 10: 10 ≤ 20 ✓ and 10 ≤ 25 ✓
Node 15: 15 ≤ 30 ✓ and 15 ≤ 35 ✓
Node 20: 20 ≤ 40 ✓

The minimum (5) floats to the top, exactly as expected.

Max-Heap vs Min-Heap Comparison
Property	Max-Heap	Min-Heap
Ordering	Parent ≥ Children	Parent ≤ Children
Root Contains	Maximum element	Minimum element
Path to Root	Values increase going up	Values decrease going up
Leaves	May contain any values	May contain any values
Extract Returns	Largest element	Smallest element
Common Use Case	Max priority queue	Min priority queue

The Duality Principle — One Structure, Two Views

Here's a profound insight that simplifies your mental model:

Duality Principle: Max-heaps and min-heaps are not two different data structures—they are the same data structure with inverted comparison operations.

Proof by Construction:

Given any max-heap storing values {v₁, v₂, ..., vₙ}, if we negate every value to get {-v₁, -v₂, ..., -vₙ}, the result is a valid min-heap with identical structure.

Why? If parent P ≥ child C in the original, then (-P) ≤ (-C) in the negated version.

Conversely, any min-heap becomes a max-heap when all values are negated.

Practical Implication

Implementation Abstraction:

In well-designed heap implementations, max-heap vs min-heap is controlled by a comparator function, not by code duplication:

// Pseudocode for a configurable heap
class Heap:
    comparator  // function(a, b) → boolean
    
    // For max-heap: comparator = (a, b) → a > b
    // For min-heap: comparator = (a, b) → a < b
    
    function parent_dominates(parent, child):
        return comparator(parent, child) or parent == child

This abstraction means:

All heap algorithms use identical logic—only the comparison differs
You can create heaps ordered by any criterion (min by age, max by priority, etc.)
Understanding one is understanding both

The Comparison Function Pattern

What the Heap Property Does NOT Guarantee

Understanding what the heap property does NOT provide is as important as understanding what it does. This clarifies the heap's role and prevents incorrect usage.

The Heap Property Does NOT Provide

•No sibling ordering — The left child could be larger or smaller than the right child. In fact, because of how insertion works, 'older' elements that should be larger might end up as right children of 'newer' smaller elements.
•No level ordering — Elements at level k are NOT guaranteed to all be larger than elements at level k+1. The heap 100→90,80→85,75,70,60 has 85 at level 3 but 80 at level 2, and 85 > 80.
•No uniqueness of structure — Many valid heap arrangements exist for the same set of values. The specific arrangement depends on insertion order.
•No efficient arbitrary search — Finding whether 42 exists in the heap is O(n)—you might need to inspect every node. There's no binary search property.
•No efficient k-th element access — Finding the 5th largest element in a max-heap requires removing 5 elements. It's not a positional structure.
•No sorted iteration — Traversing a heap (preorder, inorder, etc.) does NOT give sorted order. To get sorted output, you must repeatedly extract.

The Search Trap

The Second-Largest Element Problem:

Where is the second-largest element in a max-heap? Surprisingly, we only know it's one of the root's children.

This demonstrates that heaps provide efficient access to exactly one extreme, not to ranking in general.

The Locality Property — Subtrees as Independent Heaps

One of the most elegant properties of heaps—and one that enables elegant recursive algorithms—is that every subtree is itself a valid heap.

Locality Theorem: If a binary tree satisfies the heap property, then the subtree rooted at any node also satisfies the heap property.

Why Locality Matters

The Inductive Power of Locality:

Locality enables reasoning about heaps inductively:

Base Case: A single node (no children) trivially satisfies the heap property.

Inductive Case: If both subtrees of a node are valid heaps, and the node dominates its immediate children, then the entire tree rooted at that node is a valid heap.

This inductive structure powers:

Heapify Down: Given a node whose children are heap roots, make it a heap root too
Build Heap: Work bottom-up—leaves are already heaps, then fix progressively upward
Prove Correctness: Reason about operations by induction on tree height

Visualizing Subtree Heaps:

           100           <- root of full heap
          /   \
        90     80        <- each is root of a sub-heap
       /  \   /  \
      85  75 70  60      <- each is root of its sub-heap
     /
    50                   <- a one-node heap is trivially valid

Each encircled portion is independently a valid heap:

The subtree rooted at 90 (containing 90, 85, 75, 50) is a max-heap
The subtree rooted at 80 (containing 80, 70, 60) is a max-heap
The subtree rooted at 85 (containing 85, 50) is a max-heap
Every single-node 'subtree' is a max-heap

This recursive structure is what makes heaps 'work'—operations manipulate small portions while leaving the rest provably intact.

Heap Property Violations and Restoration

When does the heap property get violated, and how do we restore it? Understanding this prepares you for the insert and extract operations.

How Violations Occur

•Insertion: New element at the bottom might be larger than its parent (in max-heap), violating the property upward
•Extraction: After removing root and moving last element to root, the new root might be smaller than its children, violating downward
•Decrease-key: Decreasing a value might make it smaller than its children (max-heap), violating downward
•Increase-key: Increasing a value might make it larger than its parent (max-heap), violating upward

How Violations Are Fixed

•Bubble Up (Heapify Up): Swap node with parent repeatedly until parent dominates or root is reached
•Bubble Down (Heapify Down): Swap node with dominating child repeatedly until node dominates children or is a leaf
•Key insight: Only ONE direction of violation can occur at a time—a node can't simultaneously be > parent AND < children

The Single-Path Repair Property

The Bubble Up Algorithm (Preview):

function bubble_up(heap, index):
    while index > 0:
        parent_idx = (index - 1) // 2
        if heap[parent_idx] >= heap[index]:  // Max-heap: parent dominates
            break  // No violation
        swap(heap[parent_idx], heap[index])  // Fix violation
        index = parent_idx  // Move up

The Bubble Down Algorithm (Preview):

function bubble_down(heap, index, heap_size):
    while true:
        largest = index
        left = 2 * index + 1
        right = 2 * index + 2
        
        if left < heap_size and heap[left] > heap[largest]:
            largest = left
        if right < heap_size and heap[right] > heap[largest]:
            largest = right
            
        if largest == index:
            break  // No violation
        
        swap(heap[index], heap[largest])
        index = largest  // Move down

We'll explore these in detail in the operations module. For now, observe how the heap property's local nature enables simple, efficient restoration.

Choosing Between Max-Heap and Min-Heap

When solving problems, how do you decide between max-heap and min-heap? The choice relates directly to which extreme you need to access efficiently.

Problem Patterns and Heap Selection
Problem Type	Heap Choice	Reasoning
Find k largest elements	Min-heap of size k	Min-heap gives smallest of the k largest; if new element > min, replace
Find k smallest elements	Max-heap of size k	Max-heap gives largest of the k smallest; if new element < max, replace
Merge k sorted lists	Min-heap of k elements	Always extract the overall minimum from current heads
Task scheduling (earliest deadline)	Min-heap by deadline	Always process task with soonest deadline
Task scheduling (highest priority first)	Max-heap by priority	Always process task with highest priority
Dijkstra's shortest path	Min-heap by distance	Always expand node with minimum tentative distance
Huffman coding	Min-heap by frequency	Always combine two least frequent symbols
Running median	Max-heap + Min-heap	Max-heap for lower half, min-heap for upper half

The Counter-Intuitive k-Largest Pattern

The Decision Framework:

Ask yourself: Which element do I need to find or remove most often?

If you need the maximum frequently → Max-Heap
If you need the minimum frequently → Min-Heap

Then ask: Am I tracking a 'best k' set where I need to evict the worst candidate?

If tracking k largest and evicting the smallest of them → Min-heap of size k
If tracking k smallest and evicting the largest of them → Max-heap of size k

Language Default Matters

Summary: Mastering the Heap Property

We've explored the heap property in depth—the ordering invariant that gives heaps their power. Let's consolidate the key insights:

Key Takeaways

•Max-heap: Every parent ≥ its children; root is maximum. Min-heap: Every parent ≤ its children; root is minimum.
•Transitivity: The property extends to all ancestor-descendant pairs—the root dominates the entire heap.
•Duality: Max-heap and min-heap are the same structure with inverted comparison. Understanding one means understanding both.
•No sibling ordering: Left and right children have no required relationship. This is NOT a search tree.
•Locality: Every subtree is a valid heap. Operations affect only a single path.
•Single-path repair: Violations are fixed by bubbling up or down along one path—O(log n) time.
•Problem mapping: Choose max-heap to access maximum, min-heap to access minimum. For k-element tracking, use the 'opposite' heap.

What's next:

Page Complete