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

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

Invalid

      10
     /  \
   null 30

---

Heap Property

For Min Heap

Parent <= Children

For Max Heap

Parent >= Children

---

4. Types of Heap

Min Heap

        1
      /   \
     3     6
    / \   /
   5  8  9

Root contains minimum.

---

Max Heap

        20
      /    \
    15      12
   / \      /
  8  10    7

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

Tree

        2
      /   \
     5     8
    / \   /
   9 10 15

No explicit Node objects are required.

---

6. Parent/Child Formula

Suppose current index = i

Parent

(i - 1) / 2

Left Child

2 * i + 1

Right Child

2 * i + 2

Example

Array

Index

0 1 2 3 4 5

Value

2 5 8 9 10 15

Node at index 1

Value = 5

Left = 3

Right = 4

---

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];
    }
}

---

Step 2 — Resize Array

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

---

Step 3 — Insert

Algorithm

Insert at end

↓

Heapify Up

↓

Done

Implementation

public void insert(int value) {

    ensureCapacity();

    heap[size] = value;

    heapifyUp(size);

    size++;
}

---

Heapify Up

Example

Insert 3

Before

      5
     / \
    8   9

Insert

      5
     / \
    8   9
   /
  3

Swap

      5
     / \
    3   9
   /
  8

Swap Again

      3
     / \
    5   9
   /
  8

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;
    }
}

---

Step 4 — Peek

public int peek() {

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

    return heap[0];
}

---

Step 5 — Remove Root

Algorithm

Replace root

↓

Last element

↓

Delete last

↓

Heapify Down

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;
}

---

Heapify Down

Before

       10
      /  \
     4    5
    / \
   8   9

Swap

        4
      /   \
    10     5
    / \
   8  9

Swap Again

        4
      /   \
     8     5
    /
   10

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;
    }
}

---

Swap

private void swap(int i, int j) {

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

---

Build Heap

Instead of inserting one by one

9 4 8 1 5 2

We perform heapify from the last non-leaf node.

Algorithm

Start from

(n / 2) - 1

↓

Heapify Down

↓

Repeat until root

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);
    }
}

Time Complexity

O(n)

---

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;
    }
}

---

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.