堆積與優先佇列

# python
# IDEA: keep a min-heap of the k largest seen so far; its root is the kth largest
# time = O(n log k), space = O(k)
# LC 215 - Kth Largest Element in an Array
import heapq

def findKthLargest(nums, k):
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)   # drop the smallest; the k largest stay
    return min_heap[0]                # the smallest of the k largest = the kth largest

// java
// IDEA: keep a min-heap of the k largest seen so far; its root is the kth largest
// time = O(n log k), space = O(k)
// LC 215 - Kth Largest Element in an Array
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.add(num);
        if (minHeap.size() > k) {
            minHeap.poll();           // drop the smallest; the k largest stay
        }
    }
    return minHeap.peek();
}

# python
# LC 347 - Top K Frequent Elements
# IDEA: count with a hash map, then keep a min-heap of the k highest (freq, num) pairs
# time = O(n log k), space = O(n)
import heapq
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)                   # num -> frequency
    heap = []                               # (freq, num), at most k of them
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)             # evict the least frequent
    return [num for freq, num in heap]

// java
// LC 347 - Top K Frequent Elements
// IDEA: count with a hash map, then a min-heap of keys ordered by count, capped at k
// time = O(n log k), space = O(n)
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : nums) {
        count.put(n, count.getOrDefault(n, 0) + 1);
    }
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(
        (a, b) -> Integer.compare(count.get(a), count.get(b)));   // least frequent on top
    for (int key : count.keySet()) {
        minHeap.offer(key);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = minHeap.poll();          // most frequent ends up first
    }
    return result;
}

# python
# LC 347 - Top K Frequent Elements (bucket sort)
# IDEA: buckets[f] holds the values seen exactly f times; scan f from n down until k are taken
# time = O(n), space = O(n)
from collections import Counter

def topKFrequent_bucket(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]   # buckets[f] = values seen exactly f times
    for num, freq in count.items():
        buckets[freq].append(num)
    res = []
    for freq in range(len(nums), 0, -1):           # highest count first
        for num in buckets[freq]:
            res.append(num)
            if len(res) == k:
                return res
    return res

# python
# LC 23 - Merge k Sorted Lists
# IDEA: min-heap of (head value, list index, node); pop the smallest, push its successor
# time = O(N log k), space = O(k)
import heapq

def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))   # i breaks ties before node is compared
    dummy = ListNode()
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

// java
// LC 23 - Merge k Sorted Lists
// IDEA: min-heap of current list heads ordered by value; pop the smallest, offer its next
// time = O(N log k), space = O(k)
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
    for (ListNode head : lists) {
        if (head != null) {
            minHeap.offer(head);
        }
    }
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        tail.next = node;
        tail = node;
        if (node.next != null) {
            minHeap.offer(node.next);
        }
    }
    return dummy.next;
}

# python
# LC 23 - Merge k Sorted Lists (pairwise divide and conquer)
# IDEA: merge lists i and i + step for step = 1, 2, 4, ...; each round halves the number of lists
# time = O(N log k), space = O(1) extra
def mergeTwo(a, b):
    dummy = ListNode()
    tail = dummy
    while a and b:
        if a.val <= b.val:
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a else b                # one list is exhausted; append the rest
    return dummy.next

def mergeKLists_dc(lists):
    if not lists:
        return None
    step = 1
    while step < len(lists):                 # log k rounds
        for i in range(0, len(lists) - step, step * 2):
            lists[i] = mergeTwo(lists[i], lists[i + step])
        step *= 2
    return lists[0]

# python
# LC 295 - Find Median from Data Stream
# IDEA: max-heap `small` (negated) for the lower half, min-heap `large` for the upper half;
#       route every number through the other heap so the halves stay ordered and balanced
# time = O(log n) per addNum, O(1) per findMedian, space = O(n)
import heapq

class MedianFinder:
    def __init__(self):
        self.small = []   # max-heap via negation: the lower half
        self.large = []   # min-heap: the upper half; len(large) == len(small) or one more

    def addNum(self, num):
        if len(self.small) == len(self.large):
            # pass num through small so only the lower half's max moves up
            heapq.heappush(self.large, -heapq.heappushpop(self.small, -num))
        else:
            heapq.heappush(self.small, -heapq.heappushpop(self.large, num))

    def findMedian(self):
        if len(self.small) == len(self.large):
            return (self.large[0] - self.small[0]) / 2.0
        return float(self.large[0])

// java
// LC 295 - Find Median from Data Stream
// IDEA: max-heap `small` for the lower half, min-heap `large` for the upper half;
//       push through small, move its max to large, then rebalance so small is never shorter
// time = O(log n) per addNum, O(1) per findMedian, space = O(n)
class MedianFinder {
    private PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> large = new PriorityQueue<>();

    public void addNum(int num) {
        small.offer(num);
        large.offer(small.poll());          // the lower half's max crosses over: halves stay ordered
        if (large.size() > small.size()) {
            small.offer(large.poll());      // sizes: small == large or small == large + 1
        }
    }

    public double findMedian() {
        if (small.size() > large.size()) {
            return small.peek();
        }
        return (small.peek() + (double) large.peek()) / 2.0;   // widen before adding
    }
}

add  sizes equal?  routed through        small (lower)  large (upper)  median
1    yes           small -> out 1 -> large   []             [1]            1.0
2    no            large -> out 1 -> small   [1]            [2]            (1+2)/2 = 1.5
3    yes           small -> out 3 -> large   [1]            [2,3]          large[0] = 2.0

maxHeap = (-value, index)     minHeap = (value, index)
stale  <=>  index < left      (the element has fallen out of the window)

# python
# LC 1438 - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
# IDEA: two heaps hold window max/min; shrink past the older extreme; purge stale indices lazily
# time = O(N log N), space = O(N)
import heapq

class Solution(object):
    def longestSubarray(self, nums, limit):
        max_h = []   # max-heap: (-val, idx)
        min_h = []   # min-heap: ( val, idx)
        left = 0
        res = 0

        for i, v in enumerate(nums):
            heapq.heappush(max_h, (-v, i))
            heapq.heappush(min_h, (v, i))

            # window invalid -> must drop at least one of the two extremes
            while -max_h[0][0] - min_h[0][0] > limit:
                # move left PAST the earlier of the two extreme indices
                left = min(max_h[0][1], min_h[0][1]) + 1
                # lazy delete: anything left of the window is stale
                while max_h[0][1] < left:
                    heapq.heappop(max_h)
                while min_h[0][1] < left:
                    heapq.heappop(min_h)

            res = max(res, i - left + 1)

        return res

// java
// LC 1438 - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
// IDEA: max-heap + min-heap of {val, idx}; shrink past older extreme; lazy-purge stale indices
// time = O(N log N), space = O(N)
public int longestSubarray(int[] nums, int limit) {
    PriorityQueue<int[]> maxH = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));  // {val, idx}
    PriorityQueue<int[]> minH = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));

    int left = 0, res = 0;

    for (int i = 0; i < nums.length; i++) {
        maxH.offer(new int[]{nums[i], i});
        minH.offer(new int[]{nums[i], i});

        while (maxH.peek()[0] - minH.peek()[0] > limit) {
            left = Math.min(maxH.peek()[1], minH.peek()[1]) + 1;
            while (maxH.peek()[1] < left) maxH.poll();
            while (minH.peek()[1] < left) minH.poll();
        }

        res = Math.max(res, i - left + 1);
    }
    return res;
}

# python
# LC 1438 - shrink form, the inner loop only
# IDEA: left += 1 per step, purge stale tops after each step
# time = O(N log N), space = O(N)
            while -max_h[0][0] - min_h[0][0] > limit:
                left += 1
                while max_h[0][1] < left:
                    heapq.heappop(max_h)
                while min_h[0][1] < left:
                    heapq.heappop(min_h)

step  r  v  left  window     min_h[0]  max_h[0]  max-min  action                          res
1     0  8  0     [8]        (8,0)     (-8,0)    0        valid                           1
2     1  2  0     [8,2]      (2,1)     (-8,0)    6        6 > 4 -> left = 1               1
2.1   1  -  1     [2]        (2,1)     (-2,1)    0        pop (-8,0) from max_h: 0 < 1    1
3     2  4  1     [2,4]      (2,1)     (-4,2)    2        valid                           2
4     3  7  1     [2,4,7]    (2,1)     (-7,3)    5        5 > 4 -> left = 2               2
4.1   3  -  2     [4,7]      (4,2)     (-7,3)    3        pop (2,1) from min_h: 1 < 2     2

# python
# LC 253 - Meeting Rooms II
# IDEA: sort by start; min-heap of end times = rooms in use; reuse the earliest-ending room
# time = O(n log n), space = O(n)
import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    heap = [intervals[0][1]]               # end time of each room in use
    for start, end in intervals[1:]:
        if start >= heap[0]:               # the earliest-ending room is free by now
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

// java
// LC 253 - Meeting Rooms II
// IDEA: sort by start; min-heap of end times = rooms in use; reuse the earliest-ending room
// time = O(n log n), space = O(n)
public int minMeetingRooms(int[][] intervals) {
    if (intervals.length == 0) return 0;

    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    PriorityQueue<Integer> pq = new PriorityQueue<>();   // end times of rooms in use
    pq.offer(intervals[0][1]);

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= pq.peek()) {   // room frees up in time
            pq.poll();
        }
        pq.offer(intervals[i][1]);
    }

    return pq.size();
}

// java
// LC 1353 - Maximum Number of Events That Can Be Attended
// IDEA: sort by start day; each day push all events that opened, drop expired ones,
//       then attend the one with the earliest end day (min-heap)
// time = O(n log n), space = O(n)
public int maxEvents(int[][] events) {
    Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> pq = new PriorityQueue<>();   // end days of open events
    int i = 0, n = events.length, res = 0, day = 0;

    while (i < n || !pq.isEmpty()) {
        // idle -> jump to the next start day, otherwise advance one day
        day = pq.isEmpty() ? events[i][0] : day + 1;

        while (i < n && events[i][0] <= day) pq.offer(events[i++][1]);   // now open
        while (!pq.isEmpty() && pq.peek() < day) pq.poll();              // expired

        if (!pq.isEmpty()) { pq.poll(); res++; }   // attend earliest-ending event
    }
    return res;
}

# python
# LC 1405 - Longest Happy String
# IDEA: max-heap by remaining count; if the top would make 3 in a row, use the 2nd and
#       push the top back untouched; stop when only the blocked letter is left
# time = O(n log 3) = O(n), space = O(1)   n = a + b + c
import heapq

def longestDiverseString(a, b, c):
    heap = [(-cnt, ch) for cnt, ch in ((a, 'a'), (b, 'b'), (c, 'c')) if cnt > 0]
    heapq.heapify(heap)                    # negated counts: most remaining on top
    res = []
    while heap:
        cnt1, ch1 = heapq.heappop(heap)
        if len(res) >= 2 and res[-1] == ch1 and res[-2] == ch1:
            if not heap:                   # only the blocked letter is left
                break
            cnt2, ch2 = heapq.heappop(heap)
            res.append(ch2)
            if cnt2 + 1 < 0:               # counts are negative: + 1 uses one up
                heapq.heappush(heap, (cnt2 + 1, ch2))
            heapq.heappush(heap, (cnt1, ch1))   # first was NOT used
        else:
            res.append(ch1)
            if cnt1 + 1 < 0:
                heapq.heappush(heap, (cnt1 + 1, ch1))
    return "".join(res)

// java
// LC 1405 - Longest Happy String
// IDEA: max-heap by count; two-case loop:
//   Case 1: top char would create 3 consecutive -> use 2nd, put 1st back
//   Case 2: safe -> use top char directly
// time = O((a+b+c) * log 3) = O(n), space = O(1) heap size bounded by alphabet
class ValCnt {
    char val;
    int cnt;
    ValCnt(char val, int cnt) { this.val = val; this.cnt = cnt; }
}

public String longestDiverseString(int a, int b, int c) {
    PriorityQueue<ValCnt> pq = new PriorityQueue<>((x, y) -> Integer.compare(y.cnt, x.cnt));
    if (a > 0) pq.add(new ValCnt('a', a));
    if (b > 0) pq.add(new ValCnt('b', b));
    if (c > 0) pq.add(new ValCnt('c', c));

    StringBuilder sb = new StringBuilder();

    while (!pq.isEmpty()) {
        ValCnt first = pq.poll();
        int len = sb.length();

        // Case 1: adding `first` would create 3 consecutive -> use second instead
        if (len >= 2
                && sb.charAt(len - 1) == first.val
                && sb.charAt(len - 2) == first.val) {

            if (pq.isEmpty()) break;          // no alternative -> stop

            ValCnt second = pq.poll();        // use 2nd most frequent
            sb.append(second.val);
            second.cnt--;

            if (second.cnt > 0) pq.add(second);
            pq.add(first);                    // first was NOT used, put it back

        // Case 2: safe to use the most frequent character
        } else {
            sb.append(first.val);
            first.cnt--;
            if (first.cnt > 0) pq.add(first);
        }
    }

    return sb.toString();
}

# python
# LC 358 - Rearrange String k Distance Apart
# IDEA: max-heap picks the most frequent available letter; a k-long FIFO delays its return
# time = O(n log 26) = O(n), space = O(26) = O(1)
import heapq
from collections import Counter, deque

def rearrangeString(s, k):
    if k <= 1:
        return s
    heap = [(-cnt, ch) for ch, cnt in Counter(s).items()]   # negated: most remaining on top
    heapq.heapify(heap)
    cooldown = deque()                                      # (negated remaining, letter)
    res = []
    while heap:
        cnt, ch = heapq.heappop(heap)
        res.append(ch)
        cooldown.append((cnt + 1, ch))                      # one used up
        if len(cooldown) == k:                              # front has cooled for k steps
            ready_cnt, ready_ch = cooldown.popleft()
            if ready_cnt < 0:                               # still has copies left
                heapq.heappush(heap, (ready_cnt, ready_ch))
    return "".join(res) if len(res) == len(s) else ""

// java
// LC 358 - Rearrange String k Distance Apart
// IDEA: max-heap picks most frequent available char; cooldown queue locks used chars for k steps
// time = O(n log 26) = O(n), space = O(26) = O(1)
public String rearrangeString(String s, int k) {
    if (k <= 1) return s;

    int[] freq = new int[26];
    for (char c : s.toCharArray()) {
        freq[c - 'a']++;
    }

    // Max-heap ordered by remaining frequency
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(freq[b], freq[a]));
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) pq.offer(i);
    }

    // Cooldown queue: [charIndex, remainingCount]
    Queue<int[]> cooldown = new LinkedList<>();
    StringBuilder res = new StringBuilder();

    while (!pq.isEmpty()) {
        int idx = pq.poll();
        res.append((char) ('a' + idx));
        freq[idx]--;

        cooldown.offer(new int[]{idx, freq[idx]});   // enter cooldown with its remaining count

        if (cooldown.size() == k) {                  // front has cooled for k steps
            int[] ready = cooldown.poll();
            if (ready[1] > 0) {
                pq.offer(ready[0]);
            }
        }
    }

    return res.length() == s.length() ? res.toString() : "";
}

# python
# the size-k idiom, written once
import heapq

def k_largest(nums, k):                 # time = O(N log k), space = O(k)
    h = []
    for v in nums:
        if len(h) < k:
            heapq.heappush(h, v)
        elif v > h[0]:                  # peek, then replace in one sift
            heapq.heapreplace(h, v)
    return h                            # h[0] == the kth largest

def k_smallest(nums, k):                # max-heap = negate on the way in and out
    h = []
    for v in nums:
        heapq.heappush(h, -v)
        if len(h) > k:
            heapq.heappop(h)
    return [-x for x in h]              # -h[0] == the kth smallest

import heapq

# Create max heap by negating values
max_heap = [-x for x in nums]
heapq.heapify(max_heap)

# Insert into max heap
heapq.heappush(max_heap, -val)

# Get max value (remember to negate back)
max_val = -max_heap[0]  # peek
max_val = -heapq.heappop(max_heap)  # pop

# Method 1: Using tuples (automatic comparison)
heap = []
heapq.heappush(heap, (priority, data))

# Method 2: Using custom class with __lt__
class Task:
    def __init__(self, priority, data):
        self.priority = priority
        self.data = data

    def __lt__(self, other):
        return self.priority < other.priority

heap = []
heapq.heappush(heap, Task(1, "high priority"))

# python
# a heap of (key, payload) compares the payload when keys tie -> unorderable types crash.
# push a monotone counter as the second element so the comparison never reaches the payload.
import heapq, itertools

counter = itertools.count()
heapq.heappush(pq, (priority, next(counter), payload))   # FIFO among equal priorities