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

Complete Binary Tree Property

Understand how heaps maintain a complete binary tree structure where all levels except possibly the last are fully filled.

Complete Binary Tree Property

You'll learn how heaps stay efficient by maintaining a complete binary tree structure.

What Is a Complete Binary Tree?

A complete binary tree is a binary tree where every level is completely filled, except possibly the last level, which is filled from left to right with no gaps. This isn't just a nice-to-have property—it's fundamental to how heaps work efficiently.

Think of filling stadium seats row by row: you completely fill row 1, then completely fill row 2, and so on. When you get to the last row, you must fill seats starting from the left side with no empty seats in between.

Why This Matters for Heaps

Heaps use this complete structure to guarantee:

  1. Predictable height: A complete binary tree with n nodes always has height ⌊log₂ n⌋, keeping operations fast
  2. Array representation: Because there are no gaps, we can store a heap in a simple array without wasting space
  3. Efficient navigation: Parent and child relationships follow simple arithmetic formulas (parent at index i, children at 2i+1 and 2i+2)

Valid vs Invalid

Valid complete tree: Levels filled top-to-bottom, last level filled left-to-right

       1
     /   \
    2     3
   / \   /
  4   5 6

Invalid: Has a gap (node 6 exists but node 5 is missing)

       1
     /   \
    2     3
   /       \
  4         6  ❌

The complete property ensures heaps remain balanced and operations stay logarithmic, never degrading into linked-list-like linear time.

Key Takeaway: Heaps maintain a complete binary tree structure to guarantee O(log n) height, enable compact array storage, and support efficient parent-child navigation—making all heap operations predictably fast.