Heaps

A heap is a complete binary tree satisfying the heap property: min-heap (parent ≤ children) or max-heap (parent ≥ children). Backed by an array. Insert and extract in O(log n), peek in O(1). Java's PriorityQueue is a min-heap. Key use cases: Top K elements, median finding (two heaps), merge K sorted lists, task scheduling.

Key Concepts

Deep Dive: Heap Operations

Array: [1, 3, 5, 7, 9, 8]  (min-heap)

Parent of i: (i-1) / 2
Left child:   2*i + 1
Right child:  2*i + 2

// Min heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom comparator
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

Deep Dive: Top K Problems

K Largest Elements (min-heap of size K):

public int[] topKLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.stream().mapToInt(i -> i).toArray();
}
// Time: O(n log k), Space: O(k)

K Closest Points to Origin:

public int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
        (a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1]));
    for (int[] p : points) {
        maxHeap.offer(p);
        if (maxHeap.size() > k) maxHeap.poll();
    }
    return maxHeap.toArray(new int[0][]);
}

Deep Dive: Find Median from Data Stream (Two Heaps)

class MedianFinder {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // left half
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();  // right half

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
        if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll());
    }

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

Common Interview Questions

• Kth Largest Element in an Array
• Top K Frequent Elements
• Find Median from Data Stream
• Merge K Sorted Lists
• K Closest Points to Origin
• Task Scheduler