Heap — Data Structure & Algrorithm

Imagine you have a list of tasks with different priorities.

Task A → Priority 5
Task B → Priority 2
Task C → Priority 10
Task D → Priority 1

If you always want to process the task with the highest priority first, you need a way to quickly find it.

A Heap is a tree-based data structure designed for exactly this kind of problem.

A heap allows us to efficiently access the minimum or maximum element, depending on the type of heap.

There are two main types:

Min Heap → Smallest element at the top
Max Heap → Largest element at the top

What is a Heap?

A heap is a specialized binary tree that follows two important rules:

It must be a complete binary tree.
It must satisfy the heap property.

For example, a Max Heap:

The parent is always greater than or equal to its children.

Therefore, 50 is guaranteed to be the largest element.

Complete Binary Tree

The first important property of a heap is that it must be a complete binary tree.

A complete binary tree fills every level completely except possibly the last level.

The last level is filled from left to right.

For example:

This is complete.

But this is not:

because the last level isn't filled from left to right.

Max Heap

In a Max Heap, every parent is greater than or equal to its children.

For example:

The largest element is always at the root:

50
↑
Maximum

The important rule is:

Parent ≥ Children

It does not mean that every element on the left is smaller than every element on the right.

That's a common misunderstanding.

A heap is not a Binary Search Tree.

Min Heap

A Min Heap is the opposite.

Every parent is smaller than or equal to its children.

For example:

The smallest element is always at the root:

10
↑
Minimum

The rule is:

Parent ≤ Children

Max Heap vs Min Heap

The difference is simple:

Heap	Root Contains	Rule
Max Heap	Maximum	Parent ≥ Children
Min Heap	Minimum	Parent ≤ Children

For example, the same values can form:

Max Heap

Min Heap

The root changes depending on what we want to prioritize.

Heap vs Binary Search Tree

A heap and a Binary Search Tree are both tree-based structures, but their rules are different.

A BST follows:

Left < Root < Right

A heap follows:

Parent ≥ Children

for a Max Heap, or:

Parent ≤ Children

for a Min Heap.

For example:

The left child must be smaller and the right child must be larger.

But a Max Heap could be:

        50
       /  \
      70   40

Actually, this is not a valid Max Heap because 70 > 50.

A valid Max Heap would be:

        70
       /  \
      50   40

The heap only cares about the relationship between a parent and its children.

Why Is a Heap Useful?

The biggest advantage of a heap is that it gives us quick access to the highest- or lowest-priority element.

For a Max Heap:

get maximum → O(1)

For a Min Heap:

get minimum → O(1)

This makes heaps useful for:

Priority queues
Scheduling
Heap Sort
Finding the largest/smallest elements
Dijkstra's algorithm
Prim's algorithm
Top-K problems
Merging sorted data

Heap Representation Using an Array

Here's something very important about heaps.

Although we visualize a heap as a tree, we usually store it in an array.

Consider this Max Heap:

Its array representation is:

[50, 30, 40, 10, 20, 35]

We don't need to store separate left and right pointers.

The positions in the array tell us where the children are.

Parent and Child Indexes

For a 0-based array, if a node is at index i:

Left Child  = 2 * i + 1
Right Child = 2 * i + 2
Parent      = (i - 1) / 2

For example:

[50, 30, 40, 10, 20, 35]

The root is at index 0:

50 → index 0

Its children are:

2 × 0 + 1 = 1
2 × 0 + 2 = 2

So:

index 1 → 30
index 2 → 40

The tree looks like:

        50
       /  \
      30   40

For 30 at index 1:

Left  = 2 × 1 + 1 = 3
Right = 2 × 1 + 2 = 4

So:

index 3 → 10
index 4 → 20

This gives:

Inserting into a Heap

Suppose we have this Max Heap:

We want to insert 60.

First, because the tree must remain complete, we place 60 at the next available position:

But now the heap property is broken:

60 > 40

So 60 needs to move upward.

This process is called heapify up, sift up, or bubble up.

60 swaps with 40:

But:

60 > 50

So it moves up again:

Now the Max Heap property is restored.

Heapify Up

The general process is:

Insert at bottom
       ↓
Compare with parent
       ↓
Is child greater? (Max Heap)
       ↓
Yes → Swap
       ↓
Repeat

For a Min Heap, the comparison is reversed.

This is why inserting into a heap takes:

O(log n)

in the worst case.

The new element can move from the bottom to the root, and the height of a complete binary tree is O(log n).

Removing the Root

The root of a Max Heap contains the maximum value.

Suppose:

If we remove the maximum:

remove 60

we first move the last element to the root:

But now:

40 < 50

The heap property is broken.

So we move 40 downward.

This process is called heapify down, sift down, or bubble down.

Swap 40 and 50:

Now the Max Heap property is restored.

Heapify Down

The process is:

Move last element to root
          ↓
Compare with children
          ↓
Choose appropriate child
          ↓
Swap if necessary
          ↓
Repeat

For a Max Heap, we usually swap with the larger child.

For a Min Heap, we swap with the smaller child.

The time complexity is:

O(log n)

Building a Heap

Suppose we have an unsorted array:

[10, 30, 20, 5, 40, 15]

We can rearrange it into a heap.

For example, a Max Heap could become:

Array representation:

[40, 30, 20, 5, 10, 15]

The process of rearranging elements to satisfy the heap property is called heapify.

Building a heap from an array can be done in:

O(n)

time using the bottom-up heap construction algorithm.

Heap Sort

Heaps can also be used for sorting.

This algorithm is called Heap Sort.

For ascending order, we can build a Max Heap and repeatedly remove the largest element.

The general idea is:

Unsorted Array
      ↓
Build Max Heap
      ↓
Move maximum to the end
      ↓
Heapify remaining elements
      ↓
Repeat
      ↓
Sorted Array

Heap Sort has:

Time → O(n log n)
Space → O(1)

for the standard in-place implementation, excluding any implementation-specific auxiliary space.

Priority Queue

One of the most important applications of a heap is the Priority Queue.

A normal queue follows:

First In → First Out

But a priority queue processes elements according to their priority.

For example:

Task A → Priority 3
Task B → Priority 10
Task C → Priority 5

A priority queue might process:

Task B
Task C
Task A

because:

10 > 5 > 3

A heap is commonly used to implement a priority queue efficiently.

PriorityQueue in Java

Java provides a PriorityQueue class.

By default, it behaves like a Min Heap.

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        PriorityQueue<Integer> queue =
            new PriorityQueue<>();

        queue.add(30);
        queue.add(10);
        queue.add(20);

        System.out.println(queue.peek());
    }
}

Output:

The smallest element is at the top.

We can remove it:

System.out.println(queue.poll());

Output:

Then the next smallest element becomes available.

Creating a Max Heap in Java

Java's PriorityQueue is a Min Heap by default.

To create a Max Heap, we can use a reverse comparator:

import java.util.PriorityQueue;
import java.util.Collections;

class Main {
    public static void main(String[] args) {

        PriorityQueue<Integer> maxHeap =
            new PriorityQueue<>(Collections.reverseOrder());

        maxHeap.add(30);
        maxHeap.add(10);
        maxHeap.add(20);

        System.out.println(maxHeap.peek());
    }
}

Output:

Now the largest element is at the top.

Common PriorityQueue Operations

In Java:

add() / offer() → Insert
peek()           → View top
poll()           → Remove top

For example:

queue.add(50);
queue.add(20);
queue.add(30);

System.out.println(queue.peek());

For a Min Heap, this prints:

Heap Complexity

The main heap operations are:

Operation	Time Complexity
Get Min/Max	`O(1)`
Insert	`O(log n)`
Remove Min/Max	`O(log n)`
Heapify	`O(log n)`
Build Heap	`O(n)`
Search arbitrary element	`O(n)`

That last row is important.

A heap is not designed for quickly searching for an arbitrary value.

For example, if you have:

and want to find 40, you don't have a simple left/right decision like in a BST.

You may need to inspect many nodes.

So:

Heap → Excellent for min/max
BST  → Excellent for ordered searching

Heap vs Stack vs Queue

These data structures solve different problems.

A Stack follows:

LIFO
Last In, First Out

A Queue follows:

FIFO
First In, First Out

A Heap prioritizes elements:

Min Heap → Smallest first
Max Heap → Largest first

For example:

Stack:
30 → 20 → 10
30 comes out first

Queue:
10 → 20 → 30
10 comes out first

Max Heap:
50, 40, 30
50 comes out first

Real-Life Example

Imagine an emergency room.

Patients don't necessarily get treated in the order they arrive.

Instead, patients with more serious conditions are treated first.

For example:

Patient A → Priority 2
Patient B → Priority 10
Patient C → Priority 5

The order becomes:

Patient B
Patient C
Patient A

A priority queue backed by a heap is a natural way to model this type of system.

Another Real-Life Example: CPU Scheduling

Imagine several processes waiting for CPU time:

Process A → Priority 4
Process B → Priority 10
Process C → Priority 2

A priority-based scheduler can select the process with the highest priority.

A heap makes it efficient to repeatedly find and remove the highest-priority process.

Heap Applications

Heaps are used extensively in DSA and computer science.

Common applications include:

Priority queues
CPU scheduling
Task scheduling
Heap Sort
Dijkstra's algorithm
Prim's algorithm
Top-K problems
Finding K largest elements
Finding K smallest elements
Merging sorted arrays
Event scheduling

A Complete Java Example

Here's a simple Min Heap using Java's PriorityQueue:

import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {

        PriorityQueue<Integer> minHeap =
            new PriorityQueue<>();

        minHeap.add(40);
        minHeap.add(10);
        minHeap.add(30);
        minHeap.add(20);

        System.out.println("Minimum: " + minHeap.peek());

        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }
    }
}

Output:

Minimum: 10
10 20 30 40

Because the smallest element is always at the top, repeatedly calling poll() gives the elements in increasing order.

The Main Idea

A Heap is a complete binary tree that follows a special ordering rule.

For a Max Heap:

Parent ≥ Children

Example:

For a Min Heap:

Parent ≤ Children

Example:

The most important operations are:

Insert       → O(log n)
Remove root  → O(log n)
Peek root    → O(1)
Build Heap   → O(n)

And remember the key distinction:

BST  → Good for ordered searching
Heap → Good for quickly accessing min/max

A heap is a complete binary tree designed to efficiently access the highest- or lowest-priority element.

Once you understand Min Heap, Max Heap, heapify, insertion, deletion, and priority queues, you'll have the foundation needed for important algorithms such as Heap Sort, Dijkstra's Algorithm, Prim's Algorithm, and many Top-K problems.