Heap Properties and Structure Tutorial

What Are Heap Properties?

A heap is a specialized tree-based data structure that follows a specific set of structural and ordering rules. Understanding these heap properties is important because heap operations such as insertion, deletion, and heapify depend directly on them.

A binary heap has two fundamental requirements:

It must have the structure of a complete binary tree.
It must satisfy either the Min Heap or Max Heap ordering property.

1. Complete Binary Tree Property

A binary heap must always be a complete binary tree. This means every level is completely filled except possibly the last level.

Nodes on the final level must be inserted from left to right, without leaving gaps between nodes.

Valid complete binary tree:

        10
       /  \
      20   30
     / \  /
    40 50 60

The last level contains nodes from left to right, so the structure is complete.

An Incomplete Structure

The following structure is not complete because a node is missing before another node on the same level:

The node 50 occupies a position to the right while an earlier position is empty.

2. Heap-Order Property

The second fundamental property determines how values are arranged relative to their parents.

There are two primary forms:

Min Heap: Every parent is less than or equal to its children.
Max Heap: Every parent is greater than or equal to its children.

Min Heap Property

In a Min Heap, the value stored at every parent node must be less than or equal to the values stored by its children.

The relationships are:

5 ≤ 10
5 ≤ 8
10 ≤ 20
10 ≤ 15
8 ≤ 12

Therefore, 5 is guaranteed to be the smallest value in the heap.

Max Heap Property

In a Max Heap, every parent node must be greater than or equal to its children.

The root contains the largest value, 50.

Heap Property Does Not Mean Full Sorting

One of the most important things to understand about heaps is that a heap is not a fully sorted data structure.

A Min Heap guarantees that a parent is smaller than its children, but it does not guarantee an ordering between sibling nodes.

        5
       / \
      20  10

This is a valid Min Heap even though 20 is greater than 10. The rule only requires:

5 ≤ 20
5 ≤ 10

There is no requirement that the left child be smaller than the right child.

Heap Root Property

The root has a special role because the heap-order property guarantees that it contains the extreme value.

In a Min Heap, the root contains the minimum value.
In a Max Heap, the root contains the maximum value.

Min Heap:

        5
       / \
      10  8


Max Heap:

        50
       /  \
      30   40

This property makes reading the minimum or maximum element possible in O(1) time.

Heap Height Property

Because a binary heap is a complete binary tree, its height is O(log n), where n is the number of elements.

Each additional level can approximately double the number of nodes:

Level 0 → 1 node
Level 1 → 2 nodes
Level 2 → 4 nodes
Level 3 → 8 nodes
Level 4 → 16 nodes

Because the number of nodes grows exponentially with the height, the height grows logarithmically with the number of elements.

Heap Array Representation Property

The complete-tree structure allows a binary heap to be stored efficiently in an array. Parent and child relationships can be calculated using indexes.

For zero-based indexing:

Relationship	Formula
Parent of i	Math.floor((i - 1) / 2)
Left child of i	2 × i + 1
Right child of i	2 × i + 2

const heap = [5, 10, 8, 20, 15, 12];

// Index 0 → 5
// Index 1 → 10
// Index 2 → 8
// Index 3 → 20
// Index 4 → 15
// Index 5 → 12

The array above represents:

Leaf Nodes in a Heap

Leaf nodes are nodes that do not have children. In an array-based binary heap, all leaf nodes occur toward the end of the array.

For a heap with n elements, nodes from approximately Math.floor(n / 2) onward are leaves when using zero-based indexing.

Leaf nodes already satisfy the heap property locally because they have no children to compare against.

Internal Nodes

An internal node is a node with at least one child. Heapify operations primarily operate on internal nodes because leaf nodes do not need downward adjustment.

        10
       /  \
      20   30
     / \
    40 50

Internal nodes:
10, 20

Leaf nodes:
30, 40, 50

Heap Ordering Is Local

Heap ordering is a local parent-child constraint. Every parent must satisfy its relationship with its direct children.

This does not imply a sorted relationship between nodes at different branches.

This is a valid Min Heap:

5 ≤ 30
5 ≤ 10
30 ≤ 40
30 ≤ 50

The value 30 does not need to be smaller than 10.

Heap Does Not Have a Left-Smaller-Right Rule

Unlike a Binary Search Tree, a heap does not require the left child to be smaller or larger than the right child.

Min Heap:

        5
       / \
      30  10

This remains a valid Min Heap because both children are greater than the parent.

Heap Property During Insertion

A new element is initially placed at the next available position. This preserves the complete-tree property, but the heap-order property may temporarily be violated.

Heapify up restores the ordering by repeatedly comparing the new element with its parent.

Before:

        10
       /  \
      20   15

Insert 5:

        10
       /  \
      20   15
     /
    5

After heapify up:

         5
       /  \
      10   15
     /
    20

Heap Property During Extraction

When the root is removed, the last element is moved to the root. The complete-tree property remains intact, but the heap-order property may be violated.

Heapify down restores the correct parent-child relationship.

Before:

        5
       / \
      10  8
     / \
    20 15

Remove 5 and move 15:

        15
       /  \
      10    8
     /
    20

After heapify down:

         8
       /  \
      10   15
     /
    20

Heap Property and Priority

The root property makes heaps useful for priority queues. The element with the highest or lowest priority can remain at the root depending on the heap type.

A Min Heap can represent a queue where the smallest priority value is processed first.
A Max Heap can represent a queue where the largest priority value is processed first.

Min Heap priority:

        1
       / \
      3   2

Next item → priority 1

Heap Height and Operation Complexity

The complete-tree property keeps the heap height logarithmic. This directly affects operations that move an element up or down the tree.

Operation	Typical Complexity	Related Property
Peek root	O(1)	Root contains minimum or maximum
Insert	O(log n)	Heapify up through logarithmic height
Extract root	O(log n)	Heapify down through logarithmic height
Build heap	O(n)	Bottom-up heap construction
Search arbitrary value	O(n)	Heap is not globally sorted

Heap Property vs Binary Search Tree Property

Both heaps and Binary Search Trees are binary tree structures, but their ordering rules are different.

Property	Heap	Binary Search Tree
Ordering	Parent-child relationship	Subtree ordering
Shape	Complete binary tree	Not necessarily complete
Root	Minimum or maximum	Depends on insertion and balancing
Arbitrary search	O(n)	O(log n) average for balanced trees

Heap Property and Array Indexing

The complete-tree property means there is a direct relationship between a node's position and the positions of its parent and children.

const heap = [10, 20, 15, 40, 30];

const index = 1;

const parent = Math.floor((index - 1) / 2);
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;

console.log("Parent index:", parent);
console.log("Left child index:", leftChild);
console.log("Right child index:", rightChild);

For index 1, the parent is index 0, the left child is index 3, and the right child is index 4.

Heap Does Not Require Unique Values

A heap can contain duplicate values. The heap property only defines the relationship between a parent and its children.

Valid Min Heap with duplicates:

        5
       / \
      5   8
     / \
    10 10

Equal parent and child values are allowed because the Min Heap rule uses less than or equal to.

Heap Property and Duplicate Values

Duplicate values do not change the fundamental heap operations. During heapify, a swap is required only when the heap property is violated.

        10
       /  \
      10   20

No swap is necessary because 10 ≤ 10.

Heap Property and Leaf Nodes

Leaf nodes automatically satisfy the heap-order property because they have no children. There is nothing below them that can violate the parent-child rule.

This is why bottom-up heap construction starts with internal nodes rather than leaves.

Heap Properties Checklist

When identifying whether a binary tree is a valid heap, check these properties:

Is the tree complete?
Are the nodes filled from left to right on the final level?
For a Min Heap, is every parent less than or equal to its children?
For a Max Heap, is every parent greater than or equal to its children?
Is the root the minimum or maximum as required?
Are array parent and child relationships being calculated correctly?

Common Mistakes About Heap Properties

Mistaking a Heap for a Sorted Array

A heap only guarantees parent-child ordering. The complete array is not necessarily sorted.

Checking Only the Root

Having the smallest value at the root does not automatically make a tree a valid Min Heap. Every parent-child relationship must satisfy the heap property.

Forgetting the Complete-Tree Rule

A tree can satisfy the parent-child ordering and still not be a valid binary heap if its structure is not complete.

Assuming Duplicate Values Are Invalid

Duplicate values are allowed. Equal parent and child values can satisfy either heap property.

Heap Properties Summary

Property	Description
Complete structure	All levels are full except possibly the last, which fills left to right.
Min Heap order	Every parent is less than or equal to its children.
Max Heap order	Every parent is greater than or equal to its children.
Root	Contains the minimum or maximum element.
Height	O(log n)
Representation	Usually an array for binary heaps.
Duplicates	Allowed.

Key Takeaways

A binary heap must be a complete binary tree.
A Min Heap maintains parent ≤ child ordering.
A Max Heap maintains parent ≥ child ordering.
The root always contains the minimum or maximum element.
A heap is not a completely sorted structure.
Heap ordering applies to parent-child relationships, not sibling ordering.
Binary heaps can be efficiently represented using arrays.
The height of a binary heap is O(log n).
Duplicate values are allowed.
These properties are what make heap insertion and root extraction efficient.

Topics

Heap Properties and Structure