Heaps & Priority Queues: Top-K, Merge K Lists, and Two-Heap Patterns

import heapq
from typing import Any

# ── Basic heapq API ────────────────────────────────────────────────────
min_heap: list[int] = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
smallest = heapq.heappop(min_heap)          # 1 — O(log n)
peek = min_heap[0]                           # 3 — O(1), no pop
heapq.heapify(min_heap)                      # in-place heapify — O(n)

# ── Max-heap via negation ──────────────────────────────────────────────
max_heap: list[int] = []
for val in [3, 1, 4, 1, 5]:
    heapq.heappush(max_heap, -val)
largest = -heapq.heappop(max_heap)           # 5

# ── Max-heap with tuples (negation trick) ─────────────────────────────
# Push (-priority, tie_breaker, item) to get max-priority first
task_heap: list[tuple[int, int, str]] = []
counter = 0
for priority, task in [(3, "low"), (10, "high"), (5, "medium")]:
    heapq.heappush(task_heap, (-priority, counter, task))
    counter += 1
_, _, next_task = heapq.heappop(task_heap)  # "high"

# ── Top K pattern: K largest elements — O(n log k) ───────────────────
def top_k_largest(nums: list[int], k: int) -> list[int]:
    """Min-heap of size k. Root = current k-th largest."""
    heap: list[int] = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)    # evict smallest — it can't be top-k
    return sorted(heap, reverse=True)

# ── K most frequent elements (LC 347) ─────────────────────────────────
from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    """O(n log k) — count frequencies, then min-heap on frequency."""
    freq = Counter(nums)
    # min-heap of (frequency, element)
    heap: list[tuple[int, int]] = []
    for num, cnt in freq.items():
        heapq.heappush(heap, (cnt, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for _, num in heap]

# ── heapq.nlargest / nsmallest (simpler but same complexity) ──────────
result = heapq.nlargest(3, [1, 8, 2, 5, 3])    # [8, 5, 3]
# Internally: nlargest uses a min-heap of size k — same as above

import heapq
from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next

def merge_k_sorted_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    """
    Merge k sorted linked lists.
    Time: O(N log k)  — N total nodes, k lists
    Space: O(k)       — heap holds at most one node per list
    """
    dummy = ListNode(0)
    tail = dummy
    heap: list[tuple[int, int, ListNode]] = []
    counter = 0   # monotonic counter to break val ties — avoids ListNode comparison

    # Seed heap with head of each non-empty list
    for node in lists:
        if node:
            heapq.heappush(heap, (node.val, counter, node))
            counter += 1

    while heap:
        val, _, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(heap, (node.next.val, counter, node.next))
            counter += 1

    return dummy.next

import heapq

class MedianFinder:
    """
    Two-heap solution.
    addNum: O(log n)
    findMedian: O(1)
    Space: O(n)
    """
    def __init__(self):
        self.lo: list[int] = []   # max-heap (negated) — lower half
        self.hi: list[int] = []   # min-heap — upper half

    def add_num(self, num: int) -> None:
        # Step 1: Always push to lo first
        heapq.heappush(self.lo, -num)

        # Step 2: Ensure lo_max <= hi_min
        # Pop max of lo, push to hi (this enforces ordering)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))

        # Step 3: Rebalance sizes — lo should have equal or +1
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(self) -> float:
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])   # odd count: lo has the middle
        return (-self.lo[0] + self.hi[0]) / 2.0   # even: average of two middles

# ── Example ──────────────────────────────────────────────────────────
# addNum(1): lo=[-1], hi=[]       → median=1.0
# addNum(2): lo=[-1], hi=[2]      → median=1.5
# addNum(3): lo=[-2,-1], hi=[3]   → median=2.0

import heapq
from collections import defaultdict

# ── Why lazy deletion? ─────────────────────────────────────────────────
# Heaps don't support O(log n) arbitrary deletion (no find by value).
# When an element becomes invalid (e.g., already used), mark it as stale
# and skip it when popping. This avoids rebuilding the entire heap.

def k_closest_points(points: list[list[int]], k: int) -> list[list[int]]:
    """LC 973 — K closest points to origin. Max-heap of size k."""
    heap: list[tuple[float, int, int]] = []
    for x, y in points:
        dist = x * x + y * y          # squared distance (no sqrt needed for comparison)
        heapq.heappush(heap, (-dist, x, y))   # max-heap via negation
        if len(heap) > k:
            heapq.heappop(heap)
    return [[x, y] for _, x, y in heap]

def reorganize_string(s: str) -> str:
    """LC 767 — Interleave so no two adjacent chars are the same.
    Greedy: always place the most frequent remaining character."""
    from collections import Counter
    freq = Counter(s)
    max_heap = [(-cnt, ch) for ch, cnt in freq.items()]
    heapq.heapify(max_heap)

    result = []
    while len(max_heap) >= 2:
        cnt1, ch1 = heapq.heappop(max_heap)
        cnt2, ch2 = heapq.heappop(max_heap)
        result.extend([ch1, ch2])
        if cnt1 + 1 < 0:   # still has remaining count
            heapq.heappush(max_heap, (cnt1 + 1, ch1))
        if cnt2 + 1 < 0:
            heapq.heappush(max_heap, (cnt2 + 1, ch2))
    if max_heap:
        cnt, ch = max_heap[0]
        if -cnt > 1:
            return ""   # impossible: one char dominates
        result.append(ch)
    return "".join(result)