Low-Level Design (LLD) of a Heap (Priority Queue) in Java

Target Audience: Software Engineers, Backend Engineers, Java Developers, SDE Interview Preparation

Table of Contents

1. Introduction
2. What is a Heap?
3. Heap Properties
4. Types of Heap
5. Internal Representation
6. Parent/Child Index Formula
7. Designing Our Heap
8. Core Operations
9. Insert (Heapify Up)
10. Remove (Heapify Down)
11. Peek
12. Build Heap
13. Heap Sort
14. Complete Java Implementation
15. Time Complexity
16. Design Improvements
17. Java PriorityQueue Internals
18. Interview Questions
19. Summary

1. Introduction

A Heap is a specialized tree-based data structure optimized for retrieving the highest or lowest priority element efficiently.

Unlike a Binary Search Tree, a Heap does not maintain complete ordering. It guarantees that only the root node has the highest (Max Heap) or lowest (Min Heap) priority.

Common use cases:

• Priority Queue
• Task Scheduling
• CPU Scheduling
• Dijkstra’s Algorithm
• Prim’s MST
• Top K Problems
• Median Finder
• Merge K Sorted Lists
• Event Processing

2. What is a Heap?

A Heap is a Complete Binary Tree satisfying the Heap Property.

Example (Min Heap):

        2
      /   \
     5     8
    / \   /
   9  10 15

Enter fullscreen mode Exit fullscreen mode

Every parent is less than or equal to its children.

3. Heap Properties

Complete Binary Tree

Every level is completely filled except possibly the last.

Last level fills from left to right.

Example

        ✓
       10
      /  \
     20  30
    / \
   40 50

Enter fullscreen mode Exit fullscreen mode

Invalid

      10
     /  \
   null 30

Enter fullscreen mode Exit fullscreen mode

Heap Property

For Min Heap

Parent <= Children

Enter fullscreen mode Exit fullscreen mode

For Max Heap

Parent >= Children

Enter fullscreen mode Exit fullscreen mode

4. Types of Heap

Min Heap

        1
      /   \
     3     6
    / \   /
   5  8  9

Enter fullscreen mode Exit fullscreen mode

Root contains minimum.

Max Heap

        20
      /    \
    15      12
   / \      /
  8  10    7

Enter fullscreen mode Exit fullscreen mode

Root contains maximum.

5. Internal Representation

Unlike trees, Heap is stored in an Array.

Index

0 1 2 3 4 5

Array

2 5 8 9 10 15

Enter fullscreen mode Exit fullscreen mode

Tree

        2
      /   \
     5     8
    / \   /
   9 10 15

Enter fullscreen mode Exit fullscreen mode

No explicit Node objects are required.

6. Parent/Child Formula

Suppose current index = i

Parent

(i - 1) / 2

Enter fullscreen mode Exit fullscreen mode

Left Child

2 * i + 1

Enter fullscreen mode Exit fullscreen mode

Right Child

2 * i + 2

Enter fullscreen mode Exit fullscreen mode

Example

Array

Index

0 1 2 3 4 5

Value

2 5 8 9 10 15

Enter fullscreen mode Exit fullscreen mode

Node at index 1

Value = 5

Left = 3

Right = 4

Enter fullscreen mode Exit fullscreen mode

7. Designing Our Heap

We need

• Dynamic Array
• Size
• insert()
• remove()
• peek()
• heapifyUp()
• heapifyDown()
• buildHeap()

Step 1 — Heap Skeleton

public class MinHeap {

    private int[] heap;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public MinHeap() {
        heap = new int[DEFAULT_CAPACITY];
    }
}

Enter fullscreen mode Exit fullscreen mode

Step 2 — Resize Array

private void ensureCapacity() {
    if (size == heap.length) {
        heap = java.util.Arrays.copyOf(heap, heap.length * 2);
    }
}

Enter fullscreen mode Exit fullscreen mode

Step 3 — Insert

Algorithm

Insert at end

↓

Heapify Up

↓

Done

Enter fullscreen mode Exit fullscreen mode

Implementation

public void insert(int value) {

    ensureCapacity();

    heap[size] = value;

    heapifyUp(size);

    size++;
}

Enter fullscreen mode Exit fullscreen mode

Heapify Up

Example

Insert 3

Before

      5
     / \
    8   9

Insert

      5
     / \
    8   9
   /
  3

Enter fullscreen mode Exit fullscreen mode

Swap

      5
     / \
    3   9
   /
  8

Enter fullscreen mode Exit fullscreen mode

Swap Again

      3
     / \
    5   9
   /
  8

Enter fullscreen mode Exit fullscreen mode

Implementation

private void heapifyUp(int index) {

    while (index > 0) {

        int parent = (index - 1) / 2;

        if (heap[parent] <= heap[index])
            break;

        swap(parent, index);

        index = parent;
    }
}

Enter fullscreen mode Exit fullscreen mode

Step 4 — Peek

public int peek() {

    if (size == 0)
        throw new RuntimeException("Heap Empty");

    return heap[0];
}

Enter fullscreen mode Exit fullscreen mode

Step 5 — Remove Root

Algorithm

Replace root

↓

Last element

↓

Delete last

↓

Heapify Down

Enter fullscreen mode Exit fullscreen mode

Implementation

public int remove() {

    if (size == 0)
        throw new RuntimeException("Heap Empty");

    int value = heap[0];

    heap[0] = heap[size - 1];

    size--;

    heapifyDown(0);

    return value;
}

Enter fullscreen mode Exit fullscreen mode

Heapify Down

Before

       10
      /  \
     4    5
    / \
   8   9

Enter fullscreen mode Exit fullscreen mode

Swap

        4
      /   \
    10     5
    / \
   8  9

Enter fullscreen mode Exit fullscreen mode

Swap Again

        4
      /   \
     8     5
    /
   10

Enter fullscreen mode Exit fullscreen mode

Implementation

private void heapifyDown(int index) {

    while (true) {

        int left = 2 * index + 1;
        int right = 2 * index + 2;

        int smallest = index;

        if (left < size && heap[left] < heap[smallest])
            smallest = left;

        if (right < size && heap[right] < heap[smallest])
            smallest = right;

        if (smallest == index)
            break;

        swap(index, smallest);

        index = smallest;
    }
}

Enter fullscreen mode Exit fullscreen mode

Swap

private void swap(int i, int j) {

    int temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
}

Enter fullscreen mode Exit fullscreen mode

Build Heap

Instead of inserting one by one

9 4 8 1 5 2

Enter fullscreen mode Exit fullscreen mode

We perform heapify from the last non-leaf node.

Algorithm

Start from

(n / 2) - 1

↓

Heapify Down

↓

Repeat until root

Enter fullscreen mode Exit fullscreen mode

Implementation

public void buildHeap(int[] arr) {

    heap = java.util.Arrays.copyOf(arr, arr.length);

    size = arr.length;

    for (int i = (size / 2) - 1; i >= 0; i--) {
        heapifyDown(i);
    }
}

Enter fullscreen mode Exit fullscreen mode

Time Complexity

O(n)

Enter fullscreen mode Exit fullscreen mode

Complete Java Implementation

import java.util.Arrays;

public class MinHeap {

    private int[] heap;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public MinHeap() {
        heap = new int[DEFAULT_CAPACITY];
    }

    public void insert(int value) {
        ensureCapacity();
        heap[size] = value;
        heapifyUp(size);
        size++;
    }

    public int peek() {
        if (size == 0)
            throw new IllegalStateException("Heap is empty");
        return heap[0];
    }

    public int remove() {
        if (size == 0)
            throw new IllegalStateException("Heap is empty");

        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;

        if (size > 0) {
            heapifyDown(0);
        }

        return root;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void buildHeap(int[] arr) {
        heap = Arrays.copyOf(arr, Math.max(arr.length, DEFAULT_CAPACITY));
        size = arr.length;

        for (int i = (size / 2) - 1; i >= 0; i--) {
            heapifyDown(i);
        }
    }

    private void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;

            if (heap[parent] <= heap[index])
                break;

            swap(parent, index);
            index = parent;
        }
    }

    private void heapifyDown(int index) {
        while (true) {

            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int smallest = index;

            if (left < size && heap[left] < heap[smallest])
                smallest = left;

            if (right < size && heap[right] < heap[smallest])
                smallest = right;

            if (smallest == index)
                break;

            swap(index, smallest);
            index = smallest;
        }
    }

    private void ensureCapacity() {
        if (size == heap.length) {
            heap = Arrays.copyOf(heap, heap.length * 2);
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

Enter fullscreen mode Exit fullscreen mode

Time Complexity

Operation Complexity Insert O(log n) Remove O(log n) Peek O(1) Build Heap O(n) Search O(n)

Why Build Heap is O(n)?

Although heapifyDown() can take O(log n), most nodes are near the leaves and require very little work. The total cost across all nodes sums to O(n), making Floyd’s Build Heap algorithm much faster than inserting n elements individually (O(n log n)).

Java PriorityQueue Internals

Java’s PriorityQueue is implemented as a binary min-heap backed by a dynamically resized array.

Key characteristics:

• Default initial capacity: 11
• Supports natural ordering or a custom Comparator
• offer() → insert
• poll() → remove minimum
• peek() → read minimum
• Automatically grows as needed
• Not thread-safe (PriorityBlockingQueue is the concurrent alternative)

Common Interview Questions

Why use an array instead of nodes?

A complete binary tree has a predictable structure, so parent/child relationships are derived by index. This removes pointer overhead and improves cache locality.

Why is insertion O(log n)?

A new element may travel from the last level to the root during heapifyUp.

Why can’t we perform binary search on a heap?

Only the parent-child relationship is ordered. Siblings and subtrees are not globally sorted.

Difference between Heap and BST?

Heap BST Complete binary tree Ordered binary tree Root is min/max Left < Root < Right Search O(n) Search O(log n) (balanced) Peek O(1) Min/Max requires traversal

When should you use a Heap?

• Priority scheduling
• Top-K problems
• K-way merge
• Graph algorithms (Dijkstra, Prim)
• Running median
• Event simulation

Design Improvements for Production

A production-ready heap implementation would typically include:

• Generic implementation (Heap<T>)
• Support for custom Comparator<T>
• Configurable Min/Max Heap
• decreaseKey() / increaseKey() operations
• Indexed heap for efficient updates
• Bulk construction from collections
• Iterator support
• Thread-safe variant if needed
• Stable ordering for equal priorities (optional)

Summary

A Heap is one of the most fundamental data structures for implementing efficient priority-based algorithms. Understanding its array representation, heapifyUp, heapifyDown, and buildHeap operations provides a strong foundation for both coding interviews and designing high-performance scheduling, caching, and graph-processing systems.