Lesson 32Intermediate54 minAssessment-backed

Heaps and Priority Queues

Use heaps to repeatedly retrieve the most important item without fully sorting every update.

What you will be able to do

Explain heap shape and priority ordering.

Use priority queues for scheduling and top-k.

Compare heap operations with full sorting.

Implement kth-largest style logic in Java, Python, and JavaScript.

Define priority and deterministic tie-breaking.

A heap is the structure for repeated best-next retrieval. It does not fully sort all items. It only guarantees the highest or lowest priority item is available at the root.

Heap Property

In a min-heap, every parent is less than or equal to its children. The smallest item is at the root. The rest is only partially ordered, which is exactly why insertion and removal can stay logarithmic.

Min heap parent child priority property — A heap is not sorted. It is structured just enough to expose the next priority item.

Scenario: Job Scheduler

A background scheduler receives jobs with runAt timestamps. It does not need every job sorted after each insert. It needs the next due job quickly, then the next, then the next. A min-heap by runAt fits that workload.

Need	Heap behavior	Trade-off
Insert job	O(log n)	Not globally sorted.
Peek next due	O(1)	Only root guaranteed.
Pop next due	O(log n)	Reheapify after removal.
Display all sorted jobs	Repeated pops or sort	Heap alone is not final order.

Priority queue selecting next scheduled job — Priority queue answers: what should run next?

Same Pattern in Java, Python, and JavaScript

Kth largest uses a min-heap of size k. The root is the weakest value still in the winner set.

import java.util.*;

class KthLargest {
    static int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int value : nums) {
            heap.offer(value);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }
}

Assessment trap

A priority queue is not FIFO. If fairness by arrival order matters, use a queue or include arrival time as a tie-breaker.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Return the kth largest value from an unsorted array.
Return the k most frequent values.
Merge k sorted arrays into one sorted output.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Job scheduler	Sort the full job list after every insert.	Use a min-heap keyed by next run time.	Peek is O(1); push/pop are O(log n).
Top alerts dashboard	Keep all alerts fully sorted continuously.	Maintain a bounded heap for top-k or sort only when rendering.	Choose based on update/read frequency.
Merge sorted feeds	Concatenate all feeds then sort everything.	Use a priority queue with one current item from each feed.	Heap size is k streams, not total records.

Solved modelInterview Question Solutions

Question 1: Kth Largest Element

Return the kth largest value from an unsorted array. A min-heap of size k keeps exactly the k largest values seen so far; the smallest of them is the answer.

import java.util.*;

class KthLargest {
    static int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int value : nums) {
            heap.offer(value);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }
}

Question 2: Top K Frequent Elements

Return the k most frequent values. Count first, then rank frequencies. A heap is strongest when distinct cardinality is large and k is small.

import java.util.*;
class TopKFrequentHeap { static List<Integer> topK(int[] nums, int k) { Map<Integer,Integer> count = new HashMap<>(); for (int x : nums) count.put(x, count.getOrDefault(x,0)+1); PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> count.get(a) - count.get(b)); for (int x : count.keySet()) { heap.offer(x); if (heap.size() > k) heap.poll(); } return new ArrayList<>(heap); } }

Question 3: Merge K Sorted Lists

Merge k sorted arrays into one sorted output. Push the first item of each array into a priority queue. Each pop reveals the next global item and then pushes the next item from the same array.

import java.util.*;
record Entry(int value, int array, int index) {}
class MergeK { static List<Integer> merge(List<List<Integer>> lists) { PriorityQueue<Entry> pq = new PriorityQueue<>(Comparator.comparingInt(Entry::value)); for (int i = 0; i < lists.size(); i++) if (!lists.get(i).isEmpty()) pq.offer(new Entry(lists.get(i).get(0), i, 0)); List<Integer> out = new ArrayList<>(); while (!pq.isEmpty()) { Entry e = pq.poll(); out.add(e.value()); int next = e.index() + 1; if (next < lists.get(e.array()).size()) pq.offer(new Entry(lists.get(e.array()).get(next), e.array(), next)); } return out; } }

Solved modelWorked Interview Answer

Return the kth largest value from an unsorted array. Keep a min-heap of size k. After scanning all values, the root is the kth largest because only k stronger candidates remain.

import java.util.*;

class KthLargest {
    static int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int value : nums) {
            heap.offer(value);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }
}

Hands-on drillTry It Yourself

Practice task

Given stream [5,1,9,3,7] and k=3, maintain a min-heap of winners after each value.

Failure patternsCommon Mistakes to Avoid

Assuming heap is fully sorted.
Confusing min-heap and max-heap.
Forgetting tie-breakers in priority.
Using priority queue when FIFO fairness is required.
Sorting after every insertion unnecessarily.

Execution guardrailQuick-Start Checklist

Define priority key.
Choose min-heap or max-heap.
State push/pop/peek costs.
If top-k, keep heap size k.
Define tie-breaker.
State whether final output needs sorting.

Recall drillKnowledge Check

Question	Strong answer
What does heap root guarantee?	The min or max priority item, depending on heap type.
What is push/pop cost?	O(log n).
Is heap output sorted?	No, only root priority is guaranteed.

VocabularyKey Terms

Term	Meaning
Heap	Partially ordered tree-like array structure.
Priority queue	Queue where removal follows priority.
Peek	Read root without removal.
K-way merge	Merging multiple sorted streams using a heap.

Next practiceFurther Reading

Practice kth largest, top k frequent, merge k sorted lists, and task scheduler.
Study heap array indexing.
Review selection module before advanced heap problems.

Binary Search Trees

Graph Modeling