A Heap is a special tree-based data structure that follows a very simple rule: The parent node is always greater than or smaller than its child nodes. Heaps are mainly used when we want to find the largest or smallest element quickly.
Important Point About Heap
- It’s a Complete Binary Tree
- stored mostly using arrays
- NOT used for searching like BST
- used for priority-based work
Types of Heap
There are two types of heaps:
- Max Heap: In a Max Heap, the parent value is greater than both children; the largest value is always at the top (root).
50
/ \
30 40
/ \
10 202. Min Heap: In a Min Heap, the parent value is smaller than both children, the smallest value is always at the top.
10
/ \
20 30
/ \
40 50Why Heap is called a Complete Binary Tree?
A Complete Binary Tree means:
- All levels are completely filled
- Except for the last level
- Nodes are filled from left to right
Why do we use Heap?
- Priority Queue
- CPU task scheduling
- Job scheduling
- Dijkstra’s Algorithm
- Heap Sort
Heap Operations
A heap mainly supports:
- Insert – add element
- Delete – remove root
- Heapify – fix the heap property
- Peek – get top element
Max Heap Program in Java
A Heap is a complete binary tree used to manage priority-based data. In this example, we create a Max Heap using an array and perform insertion and deletion operations. This helps beginners understand how priority queues work internally.
// Max Heap implementation using array in Java
public class MaxHeap {
int[] heap;
int size;
int capacity;
public MaxHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
size = 0;
}
// Insert value
public void insert(int value) {
if (size == capacity) {
System.out.println("Heap is full");
return;
}
heap[size] = value;
int current = size;
size++;
// Fix heap (heapify up)
while (current > 0) {
int parent = (current - 1) / 2;
if (heap[current] > heap[parent]) {
int temp = heap[current];
heap[current] = heap[parent];
heap[parent] = temp;
current = parent;
} else {
break;
}
}
}
// Remove max (root)
public int removeMax() {
if (size == 0) {
System.out.println("Heap is empty");
return -1;
}
int max = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(0);
return max;
}
// Heapify down
private void heapify(int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && heap[left] > heap[largest])
largest = left;
if (right < size && heap[right] > heap[largest])
largest = right;
if (largest != index) {
int temp = heap[index];
heap[index] = heap[largest];
heap[largest] = temp;
heapify(largest);
}
}
// Print heap
public void printHeap() {
System.out.print("Heap: ");
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
// Test
public static void main(String[] args) {
MaxHeap h = new MaxHeap(10);
h.insert(10);
h.insert(40);
h.insert(20);
h.insert(50);
h.insert(30);
h.printHeap(); // Max Heap
System.out.println("Removed Max: " + h.removeMax());
h.printHeap();
}
}
Min Heap Program in Java
A Min Heap is a complete binary tree where the smallest element is always at the root. In this Java program, we implement a Min Heap using an array and perform insertion, deletion, and peek operations. This example helps beginners understand how priority queues work internally.
// Min Heap implementation using array in Java
public class MinHeap {
int[] heap;
int size;
int capacity;
// Constructor
public MinHeap(int capacity) {
this.capacity = capacity;
heap = new int[capacity];
size = 0;
}
// Insert value into heap
public void insert(int value) {
if (size == capacity) {
System.out.println("Heap is full");
return;
}
heap[size] = value;
int current = size;
size++;
// Heapify up
while (current > 0) {
int parent = (current - 1) / 2;
if (heap[current] < heap[parent]) {
int temp = heap[current];
heap[current] = heap[parent];
heap[parent] = temp;
current = parent;
} else {
break;
}
}
}
// Get minimum value
public int peek() {
if (size == 0) {
System.out.println("Heap is empty");
return -1;
}
return heap[0];
}
// Remove minimum (root)
public int removeMin() {
if (size == 0) {
System.out.println("Heap is empty");
return -1;
}
int min = heap[0];
heap[0] = heap[size - 1];
size--;
heapifyDown(0);
return min;
}
// Heapify down
private void heapifyDown(int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < size && heap[left] < heap[smallest])
smallest = left;
if (right < size && heap[right] < heap[smallest])
smallest = right;
if (smallest != index) {
int temp = heap[index];
heap[index] = heap[smallest];
heap[smallest] = temp;
heapifyDown(smallest);
}
}
// Print heap
public void printHeap() {
System.out.print("Min Heap: ");
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
// Test the Min Heap
public static void main(String[] args) {
MinHeap h = new MinHeap(10);
h.insert(40);
h.insert(10);
h.insert(30);
h.insert(50);
h.insert(20);
h.printHeap(); // Min Heap
System.out.println("Minimum value: " + h.peek());
System.out.println("Removed Min: " + h.removeMin());
h.printHeap();
}
}
How Insertion Works
- Insert value at the end
- Compare with the parent
- If smaller – swap
- Repeat until the heap rule is followed
How Deletion Works
- Remove root (minimum)
- Move the last element to the root
- Push it down to the correct position
- Heap becomes valid again