Home › DSA › Heap

Introduction to Heap

Heaps are a tree-based data structure designed for efficient priority management. They are widely used in priority queues, Dijkstra’s shortest path algorithm, heap sort, and scheduling systems. A heap is a special type of binary tree that maintains a specific order between parent and child nodes.

A heap is always a complete binary tree, meaning all levels are fully filled except possibly the last level, which is filled from left to right.

Two main types of heaps

Max Heap: Every parent node has a value greater than or equal to its children, ensuring the largest element is at the root.

Min Heap: Every parent node has a value smaller than or equal to its children, ensuring the smallest element is at the root.

Unlike a Binary Search Tree (BST), heaps do not enforce an ordering between siblings—only between parents and children. To optimize performance, heaps are commonly stored as arrays, making operations like insertion, deletion, and retrieval very efficient.

Storing a Heap in an Array

While heaps are visually represented as binary trees, they are usually stored in an array to optimize space and operations. This array representation makes insertion, deletion, and access operations more efficient without needing pointers.

Array Representation of a Heap

A heap is stored in an array by level-order traversal (also known as breadth-first order). Each node's position in the array follows a simple mathematical relationship with its parent and children:

For any node at index i:
- Left child is at index 2i + 1
- Right child is at index 2i + 2
- Parent node is at index (i - 1) / 2 (integer division)

Example: Max Heap as an Array

Let's take the Max Heap from the diagram:

The level-order traversal gives the following array representation:

16 (root) is at index 0
14 and 10 are at indices 1 and 2 (children of 16)
8, 7, 9, 3 are at indices 3, 4, 5, 6 (children of 14 and 10)
2 and 4 are at indices 7 and 8 (children of 8)

Using the formulas:

Left child of 14 (index 1) → at 2(1) + 1 = 3 → 8
Right child of 14 (index 1) → at 2(1) + 2 = 4 → 7
Parent of 9 (index 5) → at (5 - 1) / 2 = 2 → 10

Example: Min Heap as an Array

Using the Min Heap from the diagram:

The array representation is:

Using the formulas:

Left child of 21 (index 1) → at 2(1) + 1 = 3 → 24
Right child of 21 (index 1) → at 2(1) + 2 = 4 → 31
Parent of 26 (index 8) → at (8 - 1) / 2 = 3 → 24

Now, let's cover basic operations on heap:

1. Find Maximum/Minimum in a Heap

The simplest operation in a heap is retrieving the maximum or minimum element.

In a Max Heap, the largest element is always at the root (index 0 in the array representation).
In a Min Heap, the smallest element is always at the root (index 0 in the array representation).

Since heaps maintain a complete binary tree structure, accessing the maximum (for max heap) or minimum (for min heap) is a constant-time operation with complexity.

This operation is useful in priority queues, where we frequently need to fetch the highest or lowest priority element without modifying the structure of the heap.

2. Inserting Elements into a Heap (Heapify Up)

Insertion in a heap always happens at the end of the heap to maintain the complete binary tree structure. However, adding a new element may violate the heap property (Max Heap or Min Heap).

To fix this, we use the Heapify Up (also known as Percolate Up) process. This process compares the newly inserted element with its parent and swaps them if needed, ensuring that the heap property is restored. The element moves up the tree until it reaches the correct position or becomes the root. Since the height of the heap is , the **insertion operation runs in time.

Step-by-step Algorithm for Inserting an Element

Insert the new element at the last position of the heap (end of the array).
Find the parent index using the formula:

Compare the element with its parent:
- If the heap property holds (parent is greater in Max Heap, or smaller in Min Heap), stop.
- Otherwise, swap the element with its parent.
Move up the tree by setting i = parent and repeat until the root is reached or the heap property is satisfied.

Step-by-Step Example (Min Heap Insertion)

Code

java

import java.util.ArrayList;

public class Solution {

  // Heapify Up (Percolate Up) Method for Min Heap
  static void heapifyUp(ArrayList<Integer> heap, int i) {
    // Get the parent index
    int parent = (i - 1) / 2;

    // If the current node is smaller than its parent, swap
    if (i > 0 && heap.get(i) < heap.get(parent)) {
      // Swap the values
      int temp = heap.get(i);
      heap.set(i, heap.get(parent));
      heap.set(parent, temp);

      // Recursively heapify the parent node
      heapifyUp(heap, parent);
    }
  }

  // Insert a new element and heapify up
  static void insert(ArrayList<Integer> heap, int value) {
    // Add the element to the end of the heap
    heap.add(value);

    // Heapify Up from the last index
    heapifyUp(heap, heap.size() - 1);
  }

  // Print the heap
  static void printHeap(ArrayList<Integer> heap) {
    System.out.println(heap);
  }

  public static void main(String[] args) {
    ArrayList<Integer> heap = new ArrayList<>();

    // Initial Min Heap from the given example
    heap.add(13);
    heap.add(21);
    heap.add(16);
    heap.add(24);
    heap.add(31);
    heap.add(19);
    heap.add(68);
    heap.add(65);
    heap.add(26);
    heap.add(32); // Existing elements

    // Insert 14 into the heap
    insert(heap, 14);

    // Print the heap after insertion
    printHeap(heap);
  }
}

Complexity Analysis

Time Complexity

Insertion
- We always insert a new element at the last position in the heap → .
- Then, we call Heapify Up, which moves the element up the tree.
- In the worst case, the element moves up to the root, which is .
- Total Time Complexity: .
Heapify Up
- Compares at most elements (height of the heap).
- Each comparison and swap takes time.
- Total Complexity: .

Space Complexity

We use an ArrayList, which stores n elements → .
The recursion depth in Heapify Up is at most .
Since we modify the heap in place, the extra space used is .

Note: Similarway, you can insert the element into the max heap.

3. Deleting Elements from a Heap (Heapify Down)

Deletion in a heap always removes the root element (minimum in Min Heap, maximum in Max Heap). However, removing the root breaks the heap structure, so we need to restore the heap property using Heapify Down (also called Percolate Down).

The process is:

Replace the root element with the last element in the heap (to maintain the complete binary tree structure).
Compare the new root with its children and swap it with the smallest child (for Min Heap) or largest child (for Max Heap) if necessary.
Repeat the process down the tree until the heap property is restored.

Step-by-step Algorithm for Deleting the Root (Deletion in Min Heap)

Start from the Root
- Let i = 0 (starting index of the heap).
- The root element was replaced with the last element. Now, it may violate the heap property.
Identify Left and Right Children
- Find the left child of i using the formula:
- Find the right child of i using the formula:
Find the Smallest Child
- Compare the left child and right child.
- If the right child exists and is smaller than the left child, set it as the smallest.
- Otherwise, the left child is the smallest.
Compare Parent with the Smallest Child
- If the parent is smaller than or equal to the smallest child, stop (heap property is already valid).
- If the parent is larger than the smallest child, swap them.
Move Down the Tree
- Set i = smallestChildIndex (update i to the new position).
- Repeat steps 2-5 until the element is in the correct position or reaches a leaf node.
End of Algorithm
- The heap property is restored.

Step-by-Step Example (Min Heap Deletion)

We will delete 13 from the Min Heap in the given example.

Step 1: Initial Min Heap (Before Deletion)

         13
       /    \
     21      16
    /  \    /  \
   24   31 19   68
  /  \   /
 65  26 55

Array Representation: [13, 21, 16, 24, 31, 19, 68, 65, 26, 55]

Step 2: Replace Root (13) with Last Element (55)

         55
       /    \
     21      16
    /  \    /  \
   24   31 19   68
  /  \
 65  26

Array: [55, 21, 16, 24, 31, 19, 68, 65, 26]

Now, Heapify Down starts from the root (55).

Step 3: Compare 55 with Its Children (21, 16)

Smallest child = 16 (since 16 < 21).
55 > 16, so swap them.

Step 4: Swap 55 with 16

         16
       /    \
     21      55
    /  \    /  \
   24   31 19   68
  /  \
 65  26

Array: [16, 21, 55, 24, 31, 19, 68, 65, 26]

Now, Heapify Down continues from index 2 (55).

Step 5: Compare 55 with Its Children (19, 68)

Smallest child = 19 (since 19 < 68).
55 > 19, so swap them.

Step 6: Swap 55 with 19

         16
       /    \
     21      19
    /  \    /  \
   24   31 55   68
  /  \
 65  26

Array: [16, 21, 19, 24, 31, 55, 68, 65, 26]

Now, Heapify Down stops because 55 is in the correct position.

Code

java

import java.util.ArrayList;

public class Solution {

  // Heapify Down (Percolate Down) Method for Min Heap
  static void heapifyDown(ArrayList<Integer> heap, int i) {
    int size = heap.size();
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // Find the smallest child
    if (left < size && heap.get(left) < heap.get(smallest)) {
      smallest = left;
    }
    if (right < size && heap.get(right) < heap.get(smallest)) {
      smallest = right;
    }

    // If the smallest child is smaller than the parent, swap
    if (smallest != i) {
      int temp = heap.get(i);
      heap.set(i, heap.get(smallest));
      heap.set(smallest, temp);

      // Recursively heapify down
      heapifyDown(heap, smallest);
    }
  }

  // Delete the root element and heapify down
  static void deleteRoot(ArrayList<Integer> heap) {
    int size = heap.size();
    if (size == 0) {
      System.out.println("Heap is empty.");
      return;
    }

    // Replace root with last element (55 in this case)
    heap.set(0, heap.get(size - 1));

    // Remove the last element
    heap.remove(size - 1);

    // Heapify Down from root
    heapifyDown(heap, 0);
  }

  // Print the heap
  static void printHeap(ArrayList<Integer> heap) {
    System.out.println(heap);
  }

  public static void main(String[] args) {
    ArrayList<Integer> heap = new ArrayList<>();

    // Initial Min Heap before deletion
    heap.add(13);
    heap.add(21);
    heap.add(16);
    heap.add(24);
    heap.add(31);
    heap.add(19);
    heap.add(68);
    heap.add(65);
    heap.add(26);
    heap.add(55); // Last element is 55

    System.out.println("Initial Min Heap:");
    printHeap(heap);

    // Delete the root element
    deleteRoot(heap);

    System.out.println("Min Heap after deleting root:");
    printHeap(heap);
  }
}

Complexity Analysis

Time Complexity

Deletion
- Removing the root .
- Moving the last element to the root .
- Calling Heapify Down, which moves the element down the tree → .
- Total Time Complexity: .
Heapify Down
- Compares at most elements (height of the heap).
- Each comparison and swap take time.
- Total Complexity: .

Space Complexity

We use an ArrayList, which stores n elements → .
The recursion depth in Heapify Down is at most .
Since we modify the heap in place, the extra space used is .

4. Building a Heap from an Unordered Array

When given an unordered array, we can efficiently transform it into a valid heap using the Heapify Down approach. Instead of inserting elements one by one (which takes time), we use the bottom-up heap construction method, which runs in time.

The process works as follows:

Start from the last non-leaf node and call Heapify Down.
Move upward level by level, ensuring that every subtree satisfies the heap property.
Continue until the root is processed, at which point the array becomes a valid heap.

This method is efficient because it only calls heapifyDown() on half of the elements, and most calls affect only a few levels of the heap.

Algorithm for Building a Heap

Identify the last non-leaf node:
- Since leaf nodes don’t need heapifying, we start from the last non-leaf node.
- The last non-leaf node is found at index:
- This is because leaf nodes start at index n/2 in a 0-based index heap.
Heapify Down each non-leaf node in reverse order:
- Start from index (n/2 - 1) and move backward to index 0.
- Call heapifyDown() on each node to ensure the heap property is maintained.
Once the root is heapified, the entire array is now a valid heap.

Code

java

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {

  // Heapify Down (Percolate Down) Method for Min Heap
  static void heapifyDown(ArrayList<Integer> heap, int i) {
    int size = heap.size();
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // Find the smallest child
    if (left < size && heap.get(left) < heap.get(smallest)) {
      smallest = left;
    }
    if (right < size && heap.get(right) < heap.get(smallest)) {
      smallest = right;
    }

    // If the smallest child is smaller than the parent, swap
    if (smallest != i) {
      int temp = heap.get(i);
      heap.set(i, heap.get(smallest));
      heap.set(smallest, temp);

      // Recursively heapify down
      heapifyDown(heap, smallest);
    }
  }

  // Build a Heap from an Unordered Array
  static void buildHeap(ArrayList<Integer> heap) {
    int size = heap.size();
    // Start from the last non-leaf node and move upward
    for (int i = (size / 2) - 1; i >= 0; i--) {
      heapifyDown(heap, i);
    }
  }

  // Print the heap
  static void printHeap(ArrayList<Integer> heap) {
    System.out.println(heap);
  }

  public static void main(String[] args) {
    // Unordered input array
    ArrayList<Integer> heap = new ArrayList<>(
      Arrays.asList(30, 10, 50, 20, 60, 15, 70)
    );

    System.out.println("Unordered Array:");
    printHeap(heap);

    // Convert to a valid heap
    buildHeap(heap);

    System.out.println("Min Heap after building:");
    printHeap(heap);
  }
}

Complexity Analysis

Time Complexity

Heapifying a single node takes in the worst case.
We heapify approximately n/2 nodes (only non-leaf nodes).
The total complexity is , derived from the summation of log-depth heapify operations.
- A heap is a complete binary tree, where half of the nodes are leaf nodes that don’t need heapification.
- Heapify Down is called only on non-leaf nodes (approximately n/2 nodes).
- The height of a node determines how far it can move down:
  - Nodes near the bottom move only 1-2 levels.
  - The root node moves at most log n levels.
- Each Heapify Down operation takes time proportional to its height. The total cost across all nodes is given by:

Using summation properties, this simplifies to:

Thus, heap construction runs in time, making it significantly more efficient than inserting elements one by one.

Space Complexity

We use an ArrayList, which stores n elements → .
Heapify Down is done in place, so extra space usage is .

✅ Final Space Complexity: (excluding input storage).

Heap Implementation in Different Programming Languages

Here is how different languages have implemented Heap:

Language	API
C++	std::priority_queue
Java	java.util.PriorityQueue
Python	heapq
JavaScript	N/A
C#	System.Collections.Generic.PriorityQueue
Go	container/heap

🤖 Don't fully get this? Learn it with Claude

Stuck on Introduction to Heap? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Introduction to Heap** (DSA) and want to truly understand it. Explain Introduction to Heap from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Introduction to Heap** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Introduction to Heap** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Introduction to Heap** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

Heap Operations →