Course contentsShow
← Computer Science
Lesson 578 of 2,87214. Heaps and Priority QueuesFree lesson

Heap Order Property: Max-Heap

Learn the max-heap invariant where every parent node has a value greater than or equal to its children.

Heap Order Property: Max-Heap

What you'll learn: You'll understand the max-heap invariant—the rule that keeps every parent greater than or equal to its children throughout the entire tree.


The Core Idea

A max-heap is a complete binary tree where every parent node contains a value greater than or equal to the values of its children. This property must hold true at every single node in the tree, from root to leaves.

Think of it like a corporate hierarchy where every manager must have a higher salary than their direct reports. The CEO at the root has the highest salary in the company, and as you move down the tree, salaries can only stay the same or decrease—never increase.

How It Works

In a max-heap:

  • The root always contains the maximum value in the entire structure
  • For any node at position i, its value is ≥ its left child's value and ≥ its right child's value
  • Sibling nodes (children of the same parent) have no ordering requirement relative to each other
  • This property cascades down: grandparents are greater than grandchildren, and so on

Example tree:

       50
      /  \
    30    40
   / \    /
  10 20  15

Notice: 50 ≥ 30 and 50 ≥ 40; 30 ≥ 10 and 30 ≥ 20; 40 ≥ 15. Every parent dominates its children.

Why It Matters

The max-heap property guarantees instant access to the largest element—it's always at the root. This makes max-heaps perfect for priority queues where you need to repeatedly extract the maximum value efficiently.

Key Takeaway: In a max-heap, every parent node must have a value greater than or equal to both of its children, ensuring the maximum element always sits at the root.