Heap - Data Structures and Algorithms (DSA) Guide

🎯 Goal: Learn what a Heap is, why it’s important, and how to implement a basic heap data structure from scratch in Java.

📝 Table of Contents

Introduction to Heap
Heap Properties
Usage of Heap
Java’s Built-in PriorityQueue
Custom Heap Implementation
Time and Space Complexity

1️⃣ Introduction to Heap

A Heap is a specialized tree-based data structure that satisfies the heap property. It’s essentially an array visualized as a nearly complete binary tree.

2️⃣ Heap Properties

There are mainly two types of heaps:

Max-Heap: In a Max-Heap, for any given node N, the value of N is greater than or equal to the values of its children.
Min-Heap: In a Min-Heap, for any given node N, the value of N is less than or equal to the values of its children.

Heaps are essential for algorithms that require quick access to the smallest or largest elements

3️⃣ Usage of Heap

Priority Queue
Heap Sort
Graph Algorithms
Finding Largest/Smallest elements

4️⃣ Java’s Built-in PriorityQueue

Java offers a built-in PriorityQueue class, which is essentially a min-heap.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(1);
minHeap.add(2);
minHeap.add(0);
System.out.println(minHeap.poll());  // Output will be 0

5️⃣ Custom Heap Implementation

Here is a Min-Heap implementation in Java:

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

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

    private int getParentIndex(int childIndex) {
        return (childIndex - 1) / 2;
    }

    private int getLeftChildIndex(int parentIndex) {
        return 2 * parentIndex + 1;
    }

    private int getRightChildIndex(int parentIndex) {
        return 2 * parentIndex + 2;
    }

    private boolean hasParent(int index) {
        return getParentIndex(index) >= 0;
    }

    private boolean hasLeftChild(int index) {
        return getLeftChildIndex(index) < size;
    }

    private boolean hasRightChild(int index) {
        return getRightChildIndex(index) < size;
    }

    private int parent(int index) {
        return heap[getParentIndex(index)];
    }

    private int leftChild(int index) {
        return heap[getLeftChildIndex(index)];
    }

    private int rightChild(int index) {
        return heap[getRightChildIndex(index)];
    }

    private void swap(int indexOne, int indexTwo) {
        int temp = heap[indexOne];
        heap[indexOne] = heap[indexTwo];
        heap[indexTwo] = temp;
    }

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

    public int peek() {
        if (size == 0) throw new IllegalStateException();
        return heap[0];
    }

    public int poll() {
        if (size == 0) throw new IllegalStateException();
        int item = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();
        return item;
    }

    public void add(int item) {
        ensureCapacity();
        heap[size] = item;
        size++;
        heapifyUp();
    }

    private void heapifyUp() {
        int index = size - 1;
        while (hasParent(index) && parent(index) > heap[index]) {
            swap(getParentIndex(index), index);
            index = getParentIndex(index);
        }
    }

    private void heapifyDown() {
        int index = 0;
        while (hasLeftChild(index)) {
            int smallerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) < leftChild(index)) {
                smallerChildIndex = getRightChildIndex(index);
            }

            if (heap[index] < heap[smallerChildIndex]) {
                break;
            } else {
                swap(index, smallerChildIndex);
            }

            index = smallerChildIndex;
        }
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.add(5);
        minHeap.add(3);
        minHeap.add(8);

        System.out.println(minHeap.peek());  // Output will be 3
        System.out.println(minHeap.poll());  // Output will be 3
        System.out.println(minHeap.peek());  // Output will be 5
    }
}

This implementation provides add, peek, and poll methods for a Min-Heap. The heapifyUp and heapifyDown methods are used to maintain the Min-Heap property when adding and removing elements. We also handle dynamic resizing of the heap with the ensureCapacity method.

6️⃣ Time and Space Complexity

Time Complexity: Insertion, Deletion and Extraction of min/max elements happen in O(log N).
Space Complexity: O(N).