Heap Interview Problems — Unbounded Heap Freezes Dashboard

package io.thecodeforge;

import java.util.PriorityQueue;

/**
 * Implementation of the Top K pattern.
 * Time Complexity: O(N log K)
 * Space Complexity: O(K)
 * This is the exact template I copy-paste in every interview now.
 */
public class KthLargestFinder {
    public int findKthLargest(int[] nums, int k) {
        // Min-Heap to keep the largest elements at the bottom
        // and the smallest of the 'Top K' at the peek.
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.add(num);
            // If heap exceeds size K, remove the smallest element
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // The top of the heap is the K-th largest element
        return minHeap.peek();
    }

    public static void main(String[] args) {
        KthLargestFinder finder = new KthLargestFinder();
        int[] stream = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k = 4;
        System.out.println("The " + k + "th largest element is: " + finder.findKthLargest(stream, k));
    }
}

package io.thecodeforge;

import java.util.Collections;
import java.util.PriorityQueue;

public class MedianFinder {
    private PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder()); // Max-heap
    private PriorityQueue<Integer> large = new PriorityQueue<>(); // Min-heap

    public void addNum(int num) {
        // Add to max-heap, then move largest of 'small' to 'large'
        small.offer(num);
        large.offer(small.poll());

        // Keep heaps balanced: small can have at most 1 more than large
        if (small.size() < large.size()) {
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if (small.size() > large.size()) return small.peek();
        return (small.peek() + large.peek()) / 2.0;
    }
}

package io.thecodeforge;

// Building a min-heap from array using bottom-up heapify
public class HeapifyExample {
    public static void heapify(int[] arr) {
        int n = arr.length;
        // Start from last non-leaf node
        for (int i = n / 2 - 1; i >= 0; i--) {
            siftDown(arr, n, i);
        }
    }

    private static void siftDown(int[] arr, int n, int i) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] < arr[smallest]) smallest = left;
        if (right < n && arr[right] < arr[smallest]) smallest = right;

        if (smallest != i) {
            int swap = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = swap;
            siftDown(arr, n, smallest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 6, 5, 2, 4};
        heapify(arr);
        // arr is now a valid min-heap: [1, 2, 4, 5, 3, 6]
    }
}

package io.thecodeforge;

import java.util.PriorityQueue;

public class MergeKSortedLists {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) heap.offer(node);
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();
            tail.next = smallest;
            tail = tail.next;
            if (smallest.next != null) {
                heap.offer(smallest.next);
            }
        }
        return dummy.next;
    }
}

package io.thecodeforge;

import java.util.PriorityQueue;

public class SlidingWindowMaxHeap {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // Max-heap storing pairs (value, index)
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );
        int n = nums.length;
        int[] res = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            heap.offer(new int[]{nums[i], i});
            // Remove elements outside the window
            while (heap.peek()[1] <= i - k) {
                heap.poll();
            }
            // Once the first window is complete, add max to result
            if (i >= k - 1) {
                res[i - k + 1] = heap.peek()[0];
            }
        }
        return res;
    }
}