Implementing Max Heap and Min Heap in Java

Understanding Heaps

A heap is a specialized tree-based data structure that satisfies the heap property. It can be classified primarily into two types: Max Heap and Min Heap.

Max Heap: In a max heap, for any given node i, the value of i is greater than or equal to the values of its child nodes. Consequently, the largest value is found at the root.
Min Heap: Conversely, in a min heap, the value of i is less than or equal to the values of its child nodes, making the smallest value available at the root.

These properties make heaps an ideal choice for implementing priority queues where the highest or the lowest priority elements need to be accessed or removed swiftly.

Representation of Heaps

Heaps can be efficiently implemented using a complete binary tree structure. Arrays are commonly used for this representation because they allow for easy index calculations based on the properties of binary trees:

For any node at index i:
- The left child is located at index 2*i + 1
- The right child is located at index 2*i + 2
- The parent can be found at index (i - 1) / 2

Visualizing a Max Heap

Here's a simple representation of a Max Heap:

In this structure, each parent node is greater than its child nodes.

Visualizing a Min Heap

Here's a simple representation of a Min Heap:

Here, each parent node is less than its child nodes.

Implementation in Java

Now, let's dive into some code for implementing Max Heap and Min Heap in Java.

Max Heap Implementation

import java.util.Arrays;

public class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

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

    private void swap(int x, int y) {
        int temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }

    public void insert(int value) {
        if (size == capacity) {
            throw new RuntimeException("Heap is full");
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }

    private void heapifyUp(int index) {
        while (index > 0 && heap[parent(index)] < heap[index]) {
            swap(parent(index), index);
            index = parent(index);
        }
    }

    public int extractMax() {
        if(size == 0) {
            throw new RuntimeException("Heap is empty");
        }
        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return max;
    }

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

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != index) {
            swap(index, largest);
            heapifyDown(largest);
        }
    }

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(heap, size));
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(3);
        maxHeap.insert(1);
        maxHeap.insert(14);
        maxHeap.insert(7);
        maxHeap.insert(9);
        
        System.out.println("Max Heap: " + maxHeap);
        System.out.println("Extracted Max: " + maxHeap.extractMax());
        System.out.println("Max Heap after extraction: " + maxHeap);
    }
}

Min Heap Implementation

import java.util.Arrays;

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

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

    private void swap(int x, int y) {
        int temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }

    public void insert(int value) {
        if (size == capacity) {
            throw new RuntimeException("Heap is full");
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }

    private void heapifyUp(int index) {
        while (index > 0 && heap[parent(index)] > heap[index]) {
            swap(parent(index), index);
            index = parent(index);
        }
    }

    public int extractMin() {
        if(size == 0) {
            throw new RuntimeException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return min;
    }

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

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

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

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

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(heap, size));
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.insert(5);
        minHeap.insert(7);
        minHeap.insert(1);
        minHeap.insert(14);
        minHeap.insert(3);
        
        System.out.println("Min Heap: " + minHeap);
        System.out.println("Extracted Min: " + minHeap.extractMin());
        System.out.println("Min Heap after extraction: " + minHeap);
    }
}

Key Operations

Insertion

Both Max Heap and Min Heap allow for the efficient addition of elements. When you insert an element, it is initially added to the end of the heap array. The structure is then re-ordered through a process called "heapify up," ensuring the heap property remains intact.

Extraction

Extracting the maximum or minimum element involves replacing the root with the last element in the heap. After removal, the structure again undergoes "heapify down" to maintain order.

Applications of Heaps

Priority Queues: Essential for scheduling tasks based on priority.
Heap Sort: An efficient sorting algorithm utilizing heaps.
Graph Algorithms: Such as Dijkstra's shortest path algorithm.
Event Simulation: Managing events in time-based simulations effectively.

Through this exploration of Max Heaps and Min Heaps, you should have gained insights into their implementation and relevance in data structures and algorithms. Understanding these concepts not only enhances your programming skills but also equips you for technical interviews where heaps frequently appear as a topic of discussion.