🚀 Blog 7: Heap & Priority Queue — Expedia DSA Prep

Expedia loves to test whether you can leverage heaps (priority queues) for problems like:

Top-K retrieval
Merging multiple sorted lists
Streaming median computation

We’ll cover:

Top K Frequent Elements
Merge K Sorted Lists
Find Median from Data Stream

🔹 Problem 1: Top K Frequent Elements

Pattern: HashMap + Min Heap

📌 Find the K most frequent elements in an array.

import java.util.*;

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

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

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

        int[] res = new int[k];
        int i = 0;
        while (!minHeap.isEmpty()) {
            res[i++] = minHeap.poll().getKey();
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,1,2,2,3};
        System.out.println(Arrays.toString(topKFrequent(arr, 2))); // [1,2]
    }
}

✅ Time Complexity: O(N log K)

🔹 Problem 2: Merge K Sorted Lists

Pattern: Min Heap

📌 Merge K sorted linked lists into one sorted list.

import java.util.*;

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

public class MergeKLists {
    public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

        for (ListNode node : lists)
            if (node != null) pq.offer(node);

        ListNode dummy = new ListNode(0), curr = dummy;

        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            curr.next = node;
            curr = curr.next;
            if (node.next != null) pq.offer(node.next);
        }
        return dummy.next;
    }
}

✅ Time Complexity: O(N log K), where N = total nodes

🔹 Problem 3: Find Median from Data Stream

Pattern: Two Heaps (Max Heap + Min Heap)

📌 Continuously add numbers and return median efficiently.

import java.util.*;

class MedianFinder {
    private PriorityQueue<Integer> left;  // max heap
    private PriorityQueue<Integer> right; // min heap

    public MedianFinder() {
        left = new PriorityQueue<>(Collections.reverseOrder());
        right = new PriorityQueue<>();
    }

    public void addNum(int num) {
        left.offer(num);
        right.offer(left.poll());

        if (left.size() < right.size())
            left.offer(right.poll());
    }

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

    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();
        mf.addNum(1);
        mf.addNum(2);
        System.out.println(mf.findMedian()); // 1.5
        mf.addNum(3);
        System.out.println(mf.findMedian()); // 2
    }
}