Heap / Priority Queue

7 questions. A heap maintains one weak guarantee — parent before children — and that's exactly enough to expose an extreme in O(1) while costing only O(log n) to update.

The one idea

Sorting gives you complete order for O(n log n). If you only ever need the minimum (or the maximum), that's far more than you're paying for.

Operation	Cost
See the extreme	`O(1)`
Insert	`O(log n)`
Remove the extreme	`O(log n)`
Find an arbitrary element	`O(n)` — there's no order to exploit

That last row is the price. A heap is useless for lookup, and that's why removing a specific value is the recurring pain point in the follow-ups.

The inversion that trips everyone up

To keep the k largest, use a min-heap of size k

Min-heap for the k LARGEST. Max-heap for the k SMALLEST.

The heap is always inverted relative to the wording, because the root is the eviction candidate, not the answer. Keeping the k largest means the thing to discard is the smallest of them — so that's what must sit at the root.

Questions 1, 3 and 4 are all this same move.

Easy Kth Largest Element in a Stream LC 703 12 min Easy Last Stone Weight LC 1046 10 min Medium K Closest Points to Origin LC 973 13 min Medium Kth Largest Element in an Array LC 215 14 min Medium Task Scheduler LC 621 13 min Medium Design Twitter LC 355 13 min Hard Find Median from Data Stream LC 295 13 min

When a heap is NOT the answer

Two of the seven have better solutions, which is worth knowing before reaching for a PriorityQueue reflexively:

Question 4 — with the whole array in memory, quickselect is O(n) average versus the heap's O(n log k).

Question 5 — the greedy heap simulation is correct but does work proportional to the answer, which can dwarf the input. The frequency formula is O(n).

The most frequent task dictates the layout

The heap wins when data streams, when k ≪ n, or when the collection changes between extractions.

Two heaps for the median

A heap exposes an extreme; the median is the element furthest from both extremes. Split the data at the median and each half's adjacent element becomes an extreme.

The add is three unconditional lines — offer to the max-heap, push its root across to the min-heap, then rebalance. The routing enforces the ordering, so there are no comparisons and no boundary cases. The order matters: rebalancing before transferring can break the invariant.

The traps

Trap	Symptom
Max-heap for the k largest (Q1, Q4)	The element you need is buried at a leaf
`TreeSet` instead of a heap (Q1)	Duplicates collapse — silently wrong rank
Pushing a zero stone (Q2)	A phantom stone can be returned as the answer
`!isEmpty()` instead of `size() > 1` (Q2)	`poll()` returns null → NPE on unboxing
Computing `√` (Q3)	Needless floating point; `x² + y²` orders identically
`k - 1` instead of `n - k` (Q4)	Plausible wrong answer, not a crash
Deterministic pivot (Q4)	`O(n²)` on sorted input — measured 595× worse
Formula without `max(tasks.length, …)` (Q5)	Undercounts when the gaps overflow
`List` instead of `Set` for follows (Q6)	Double-follow duplicates tweets in the feed
Forgetting self-inclusion (Q6)	Your own tweets silently vanish from your feed
`/ 2` instead of `/ 2.0` (Q7)	1.5 truncates to 1.0

Java notes

Java

new PriorityQueue<>()                              // min-heap (the default)
new PriorityQueue<>(Comparator.reverseOrder())     // max-heap
new PriorityQueue<>(existingCollection)            // O(n) heapify — natural ordering only

Permits duplicates, forbids nulls. Duplicates matter for correct ranks.
(a, b) -> b - a overflows. Use Comparator.reverseOrder() or comparingInt.
reversed() reverses the whole chain, not just the last key.
Iterating a PriorityQueue is not sorted — only repeated poll is.
remove(Object) is O(n). This is what makes deletion follow-ups hard; the standard fix is lazy deletion.

Verification

Every snippet compiled and cross-checked against an independent implementation — 3,000+ randomized cases:

Q1 against a sort-everything reference, 400 streams × 25 adds
Q2 against a re-sort-each-round reference, 504 cases
Q3 across all three implementations, comparing distance multisets rather than point sets, since ties make the chosen points ambiguous
Q4 across sort, heap and quickselect, 502 cases
Q5 formula verified against the greedy simulation, 506 cases
Q6 against a collect-and-sort reference, 300 traces × 60 mixed operations
Q7 against a sort reference over random, ascending and descending streams — the last two exercise the rebalance in opposite directions

Four deliberately-broken variants confirm the traps:

a TreeSet-backed Q1 returns 3 instead of 5 for the stream 5, 3, 5 with k = 2
the Q5 formula without the max returns 7 instead of 10 on AAABCDEFGH with n = 2
Q7 with / 2 returns 1.0 instead of 1.5
a last-element pivot on a sorted array of 4,000 scans 8,001,999 elements to find the minimum versus 13,455 with a random pivot — and, notably, only 4,000 to find the maximum, so the worst case needs sorted input and an unlucky k