EP.20 — Heap：
永遠能找到最大或最小

import heapq

# === Min-Heap（預設）===
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)

heap[0]               # 查看最小值，O(1)  → 1
heapq.heappop(heap)   # 彈出最小值，O(log n) → 1

# 直接從 list 建 heap，O(n)（比逐一 push 快）
nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)   # in-place，O(n)

# heapreplace：pop + push，比分開做快（只做一次 sift）
heapq.heapreplace(heap, new_val)

# === Max-Heap（用負值模擬）===
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)

-max_heap[0]          # 最大值 → 4
-heapq.heappop(max_heap)  # 彈出最大值 → 4

# === 帶 key 的元素（存 tuple）===
# tuple 比較從第一個元素開始，第一個相同才比第二個
heapq.heappush(heap, (freq, word))  # 先按 freq 排序

import heapq

def findKthLargest(nums: list[int], k: int) -> int:
    heap = []   # min-heap，大小維持在 k

    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)   # 彈出最小的，保留前 k 大

    return heap[0]   # 堆頂就是第 k 大

# 更簡潔的寫法：heapq.nlargest 直接搞定
def findKthLargest_v2(nums: list[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]   # 前 k 大中最小的

from collections import Counter
import heapq

def topKFrequent(nums: list[int], k: int) -> list[int]:
    # Step 1：統計頻率
    count = Counter(nums)   # {num: freq}

    # Step 2：min-heap（按頻率排），維持大小 k
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)   # 踢掉頻率最低的

    return [num for freq, num in heap]

# nums=[1,1,1,2,2,3], k=2
# count = {1:3, 2:2, 3:1}
# 最終 heap = [(2,2), (3,1)]（頻率 2 和 3）
# 回傳 [2, 1]

def topKFrequent_bucket(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)

    # bucket[i] = 出現頻率恰好為 i 的所有元素
    bucket = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)

    # 從高頻率往低頻率取，直到取夠 k 個
    result = []
    for freq in range(len(bucket) - 1, 0, -1):
        result.extend(bucket[freq])
        if len(result) >= k:
            return result[:k]

    return result

# nums=[1,1,1,2,2,3], k=2
# bucket[1]=[3], bucket[2]=[2], bucket[3]=[1]
# 從後往前：取 bucket[3]=[1] → result=[1]
#           取 bucket[2]=[2] → result=[1,2]，夠了！

import heapq

class MedianFinder:
    def __init__(self):
        self.left  = []   # max-heap（存負值）：較小的一半
        self.right = []   # min-heap：較大的一半

    def addNum(self, num: int) -> None:
        # Step 1：先 push 到 left（max-heap）
        heapq.heappush(self.left, -num)

        # Step 2：確保 left 的最大值 ≤ right 的最小值
        if self.right and (-self.left[0]) > self.right[0]:
            val = -heapq.heappop(self.left)
            heapq.heappush(self.right, val)

        # Step 3：平衡大小，讓 left 最多比 right 多 1 個
        if len(self.left) > len(self.right) + 1:
            val = -heapq.heappop(self.left)
            heapq.heappush(self.right, val)
        elif len(self.right) > len(self.left):
            val = heapq.heappop(self.right)
            heapq.heappush(self.left, -val)

    def findMedian(self) -> float:
        if len(self.left) > len(self.right):
            return -self.left[0]             # left 多一個，它就是中位數
        return (-self.left[0] + self.right[0]) / 2.0   # 兩側等長，取平均