EP.20 — Heap：
從 Top K Frequent 往底層理解

from collections import Counter

nums = [1, 1, 1, 2, 2, 3]

# Counter 是 collections 模組提供的計數工具
# 它會回傳一個類似 dict 的物件：
# key   = 元素本身
# value = 這個元素出現幾次
count = Counter(nums)

print(count)
# Counter({1: 3, 2: 2, 3: 1})

from collections import Counter

def topKFrequent(nums: list[int], k: int) -> list[int]:
    # Step 1：先統計每個數字出現幾次
    # nums = [1,1,1,2,2,3]
    # count = Counter({1: 3, 2: 2, 3: 1})
    count = Counter(nums)

    # Step 2：most_common(k) 會依照「出現次數」由高到低排序
    # 並回傳前 k 組 (num, freq)
    # k = 2 時，top_k = [(1, 3), (2, 2)]
    top_k = count.most_common(k)

    # Step 3：LeetCode 只要回傳 num，不需要 freq
    # 所以用串列生成式把 [(1,3), (2,2)] 轉成 [1,2]
    return [num for num, freq in top_k]

# nums = [1,1,1,2,2,3], k = 2
# count.most_common(2) -> [(1, 3), (2, 2)]
# return [1, 2]

top_k = [(1, 3), (2, 2)]

# 寫法一：一般 for loop
result = []
for num, freq in top_k:
    # num  是數字本身，例如 1
    # freq 是出現次數，例如 3
    # 題目只要數字，所以只 append num
    result.append(num)

# 寫法二：串列生成式
# 格式：[要放進新 list 的值 for 每一筆資料 in 原本的資料]
result = [num for num, freq in top_k]

# result = [1, 2]

from collections import Counter
import heapq

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

    # Step 2：取得所有不重複的數字
    # candidates = dict_keys([1, 2, 3])
    candidates = count.keys()

    # Step 3：定義比較規則
    # nlargest 要找「最大」，但這題不是比數字大小
    # 而是比每個數字出現的頻率
    def get_frequency(num: int) -> int:
        return count[num]

    # Step 4：從 candidates 裡找出 get_frequency 最大的 k 個
    result = heapq.nlargest(
        k,                 # 要取前 k 大
        candidates,        # 候選資料：1, 2, 3
        key=get_frequency, # 比較規則：看 count[num]
    )

    return result

# get_frequency(1) -> 3
# get_frequency(2) -> 2
# get_frequency(3) -> 1
# heapq.nlargest(2, candidates, key=get_frequency) -> [1, 2]

from collections import Counter
import heapq

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

    # lambda num: count[num]
    # 等同於：
    #
    # def get_frequency(num):
    #     return count[num]
    #
    # 這裡用 lambda，是因為比較規則只有一行
    return heapq.nlargest(
        k,
        count.keys(),
        key=lambda num: count[num],
    )

from collections import Counter
import heapq

# key=lambda x: x 代表：
# 如果呼叫者沒有指定比較規則，就直接用 item 本身來比較
def my_nlargest(k, iterable, key=lambda x: x):
    heap = []  # 這會是一個 min-heap

    for item in iterable:
        # score 是這個 item 的比較分數
        # 在 #347 裡，item 是 num，score 是 count[num]
        score = key(item)

        # heap 裡放 (score, item)
        # Python 會先比較 tuple 的第一個值 score
        heapq.heappush(heap, (score, item))

        # heap 只保留 k 個元素
        # 如果超過 k，就把目前 score 最小的踢掉
        if len(heap) > k:
            heapq.heappop(heap)

    # heap 裡剩下的就是 score 最大的 k 個 item
    # 但 heap 裡存的是 (score, item)，所以要把 item 抽出來
    return [item for score, item in heap]

def topKFrequent(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    return my_nlargest(k, count.keys(), key=lambda num: count[num])

# heappush：先放到最後，再往上調整
heapq.heappush(heap, (1, 3))

# heappop：拿走 heap[0]，把最後一個補到 root，再往下調整
smallest = heapq.heappop(heap)

# 所以每次調整只會走樹高
# 完全二元樹高度約為 log k
# 因此 heappush / heappop 都是 O(log k)

import heapq

nums = [5, 1, 9, 3, 7]

# 查前 k 大
largest = heapq.nlargest(2, nums)
# [9, 7]

# 查前 k 小
smallest = heapq.nsmallest(2, nums)
# [1, 3]

from collections import Counter
import heapq

def bottomKFrequent(nums: list[int], k: int) -> list[int]:
    # Step 1：統計每個數字出現幾次
    # nums = [1,1,1,2,2,3,4]
    # count = Counter({1: 3, 2: 2, 3: 1, 4: 1})
    count = Counter(nums)

    # Step 2：候選資料是所有不重複的數字
    # candidates = dict_keys([1, 2, 3, 4])
    candidates = count.keys()

    # Step 3：比較規則是「出現頻率」
    # num=1 -> count[1] = 3
    # num=3 -> count[3] = 1
    def get_frequency(num: int) -> int:
        return count[num]

    # Step 4：找出頻率最小的 k 個元素
    # nsmallest 會依照 key(num) 的結果由小到大取前 k 個
    return heapq.nsmallest(
        k,
        candidates,
        key=get_frequency,
    )

# nums = [1,1,1,2,2,3,4], k = 2
# 頻率：1->3, 2->2, 3->1, 4->1
# bottomKFrequent(nums, 2) -> [3, 4]

from collections import Counter
import heapq

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

    # 縮寫版：
    # key=lambda num: count[num]
    # 代表每個 num 都用 count[num] 當作比較分數
    return heapq.nsmallest(
        k,
        count.keys(),
        key=lambda num: count[num],
    )

import heapq

# 1. heappush：放入元素，並維持 min-heap
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
# heap[0] 永遠是最小值 -> 1

# 2. heappop：取出並移除最小值
smallest = heapq.heappop(heap)
# smallest = 1

# 3. heapify：把普通 list 原地轉成 heap
nums = [5, 1, 9, 3]
heapq.heapify(nums)
# nums 現在符合 heap 規則，nums[0] 是最小值

# 4. heappushpop：先 push，再 pop 最小值
# 適合「加入新元素後，仍然只想保留較大的那些」的情境
removed = heapq.heappushpop(nums, 4)

# 5. heapreplace：先 pop 最小值，再 push 新元素
# 注意：即使新元素比較小，也一定會先移除原本的 heap[0]
removed = heapq.heapreplace(nums, 6)

# 6. nlargest / nsmallest：直接取前 k 大或前 k 小
top_2 = heapq.nlargest(2, nums)
bottom_2 = heapq.nsmallest(2, nums)