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

Heap Structure Invariants

Identify the two core invariants (complete tree shape and heap order) that must be maintained in all heap operations.

Heap Structure Invariants

What you'll learn: You'll learn the two fundamental rules that every heap must obey at all times to function correctly.

The Two Core Invariants

A heap isn't just any binary tree—it must satisfy two strict invariants (unchanging rules) simultaneously:

1. Complete Tree Shape Invariant

The tree must be complete: all levels are completely filled except possibly the last, which fills from left to right with no gaps. This means you can't have a node on the right side of a level if there's an empty spot on the left.

Think of stadium seating where people fill rows from left to right, front to back—no one sits in row 5 until row 4 is completely full.

2. Heap Order Invariant

Every node must satisfy the heap order property relative to its children:

  • Min-heap: Every parent is ≤ both children
  • Max-heap: Every parent is ≥ both children

This relationship must hold for every single parent-child pair in the tree—no exceptions.

Why Both Matter

These invariants work together:

  • The shape invariant guarantees O(log n) height and enables efficient array representation
  • The order invariant ensures the root always holds the minimum (or maximum) element

Every heap operation—insertion, deletion, heapify—must preserve both invariants. If you violate the shape, you lose the array efficiency. If you violate the order, you lose the priority guarantee.

Key Takeaway: The two heap invariants—complete tree shape and heap order property—must both be maintained after every operation; together they give heaps their O(log n) performance and constant-time access to the min/max element.