Heap Data Structure in Java – Implementation and Explanation

A Heap is a special tree-based data structure that satisfies the heap property:

• In a Min Heap, the parent node is always smaller than or equal to its children.
• In a Max Heap, the parent node is always greater than or equal to its children.

This blog will cover:

1. Heap properties and use cases
2. Implementation of Min Heap and Max Heap in Java
3. Heap operations (insert, delete, extract, heapify, etc.)
4. Use cases of heaps in system design

---

1️⃣ Heap Properties and Use Cases

Properties of Heap:

• A Complete Binary Tree: All levels are completely filled except possibly the last level, which is filled from left to right.
• Heap Order Property:
  • Min Heap: A[parent] ≤ A[child]
  • Max Heap: A[parent] ≥ A[child]

Use Cases of Heaps:

• Priority Queue: Efficiently retrieves the highest/lowest priority element.
• Heap Sort: Sorting technique using a heap.
• Dijkstra's Algorithm: Uses a Min Heap to find the shortest path.
• Scheduling Algorithms: Used in OS process scheduling.
• Median Finding: A combination of min and max heaps helps maintain the median in a stream of numbers.

---

2️⃣ Min Heap Implementation in Java

Min Heap Class with Insert and Delete Operations

import java.util.ArrayList;

class MinHeap {
    private ArrayList<Integer> heap;

    public MinHeap() {
        heap = new ArrayList<>();
    }

    private int parent(int i) { return (i - 1) / 2; }
    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }

    public void insert(int value) {
        heap.add(value);
        int current = heap.size() - 1;

        // Bubble up
        while (current > 0 && heap.get(current) < heap.get(parent(current))) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    public int extractMin() {
        if (heap.isEmpty()) throw new IllegalStateException("Heap is empty");

        int min = heap.get(0);
        heap.set(0, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        heapifyDown(0);
        return min;
    }

    private void heapifyDown(int i) {
        int smallest = i;
        int left = leftChild(i);
        int right = rightChild(i);

        if (left < heap.size() && heap.get(left) < heap.get(smallest))
            smallest = left;

        if (right < heap.size() && heap.get(right) < heap.get(smallest))
            smallest = right;

        if (smallest != i) {
            swap(i, smallest);
            heapifyDown(smallest);
        }
    }

    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    public void printHeap() {
        System.out.println(heap);
    }
}

public class MinHeapTest {
    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap();
        minHeap.insert(10);
        minHeap.insert(20);
        minHeap.insert(5);
        minHeap.insert(30);
        minHeap.insert(2);

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

        System.out.println("Extract Min: " + minHeap.extractMin());
        minHeap.printHeap();
    }
}

Output

Min Heap: 
[2, 10, 5, 30, 20]
Extract Min: 2
[5, 10, 20, 30]

---

3️⃣ Max Heap Implementation in Java

Max Heap Class with Insert and Delete Operations

import java.util.ArrayList;

class MaxHeap {
    private ArrayList<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<>();
    }

    private int parent(int i) { return (i - 1) / 2; }
    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }

    public void insert(int value) {
        heap.add(value);
        int current = heap.size() - 1;

        // Bubble up
        while (current > 0 && heap.get(current) > heap.get(parent(current))) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    public int extractMax() {
        if (heap.isEmpty()) throw new IllegalStateException("Heap is empty");

        int max = heap.get(0);
        heap.set(0, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        heapifyDown(0);
        return max;
    }

    private void heapifyDown(int i) {
        int largest = i;
        int left = leftChild(i);
        int right = rightChild(i);

        if (left < heap.size() && heap.get(left) > heap.get(largest))
            largest = left;

        if (right < heap.size() && heap.get(right) > heap.get(largest))
            largest = right;

        if (largest != i) {
            swap(i, largest);
            heapifyDown(largest);
        }
    }

    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    public void printHeap() {
        System.out.println(heap);
    }
}

public class MaxHeapTest {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        maxHeap.insert(30);
        maxHeap.insert(2);

        System.out.println("Max Heap: ");
        maxHeap.printHeap();

        System.out.println("Extract Max: " + maxHeap.extractMax());
        maxHeap.printHeap();
    }
}

Output

Max Heap: 
[30, 20, 5, 10, 2]
Extract Max: 30
[20, 10, 5, 2]

---

4️⃣ System Design Use Cases of Heaps

• Real-Time Task Scheduling: Operating systems use Min Heaps to schedule jobs based on priority.
• Network Traffic Management: Max Heaps help in prioritizing high-traffic nodes.
• Memory Management: Heap memory allocation in programming languages like Java.
• Database Query Optimization: Heaps are used in indexing and query optimization.

---

5️⃣ Conclusion

Heaps are an essential data structure for priority-based processing. In this blog, we implemented both Min Heap and Max Heap in Java, discussed their operations, and explored real-world use cases.

Would you like to see a Heap Sort implementation next? Let me know in the comments!