Heaps-(Theory)

1. What is a Heap?

A heap is a specialized binary tree-based data structure that satisfies the heap property:

• Max-Heap: Every parent node ≥ its children.

• Min-Heap: Every parent node ≤ its children.

A heap is a complete binary tree, meaning all levels are filled except possibly the last, which is filled from left to right.

Heaps are commonly implemented as arrays, where:

• Left child of index i: 2*i + 1

• Right child of index i: 2*i + 2

• Parent of index i: (i - 1) / 2

2. Java Heap Implementation

Max-Heap in Java (Custom Class)

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

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        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; }

    public void insert(int value) {
        if (size == capacity) throw new IllegalStateException("Heap is full");
        heap[size] = value;
        int current = size++;
        while (current > 0 && heap[current] > heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

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

    private void downHeapify(int i) {
        int current = i;
        while (leftChild(current) < size) {
            int larger = leftChild(current);
            if (rightChild(current) < size && heap[rightChild(current)] > heap[larger]) {
                larger = rightChild(current);
            }
            if (heap[current] >= heap[larger]) break;
            swap(current, larger);
            current = larger;
        }
    }

    private void swap(int i, int j) {
        int tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp;
    }
}

3. Heap Sort (In-place Sorting using Heap)

Idea:

1. Build a max-heap.

2. Swap root with last element and reduce heap size.

3. Heapify the root again.

public class HeapSort {
    public void sort(int[] arr) {
        int n = arr.length;

        // Step 1: Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // Step 2: One by one extract elements
        for (int i = n - 1; i > 0; i--) {
            int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
            heapify(arr, i, 0);
        }
    }

    private void heapify(int[] arr, int n, int i) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;

        if (largest != i) {
            int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

4. Common Heap-Based Patterns

Top-K Elements (Min-Heap of size K)

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.peek();
}

🔹 K-th Smallest (Max-Heap of size K)

public int findKthSmallest(int[] nums, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int num : nums) {
        maxHeap.offer(num);
        if (maxHeap.size() > k) maxHeap.poll();
    }
    return maxHeap.peek();
}

Merge K Sorted Lists

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode node : lists) if (node != null) minHeap.offer(node);
    
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        tail.next = node;
        tail = tail.next;
        if (node.next != null) minHeap.offer(node.next);
    }
    return dummy.next;
}

Median in Data Stream (Two Heaps)

class MedianFinder {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) maxHeap.offer(num);
        else minHeap.offer(num);

        if (maxHeap.size() > minHeap.size() + 1)
            minHeap.offer(maxHeap.poll());
        else if (minHeap.size() > maxHeap.size())
            maxHeap.offer(minHeap.poll());
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size())
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        return maxHeap.peek();
    }
}

Meeting Rooms II

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    heap.offer(intervals[0][1]);

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= heap.peek()) heap.poll();
        heap.offer(intervals[i][1]);
    }
    return heap.size();
}

Top K Frequent Elements

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);

    PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
        new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());

    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
        minHeap.offer(entry);
        if (minHeap.size() > k) minHeap.poll();
    }

    int[] result = new int[k];
    for (int i = 0; i < k; i++) result[i] = minHeap.poll().getKey();
    return result;
}

5. Java PriorityQueue Essentials

6. Heap Time and Space Complexity

7. Optimization Insights

• Use Min-Heap of size K for Top K problems → reduces time to O(n log k).

• For Merge K Sorted Lists, always track head nodes only → reduces memory.

• For Median, balance two heaps: max-heap (lower half) and min-heap (upper half).

• Use iterative heapify in sorting to avoid stack overflow on large data.

• Avoid frequent object creation in tight loops (use object pooling or reuse where possible).

8. Key Use-Cases for Heaps