1.1 Heap là gì?

Heap được lưu dưới dạng mảng: cha tại i, con trái tại 2i+1, con phải tại 2i+2. Mảng nhỏ gọn → ít overhead so với cây thực sự.

1.2 heapq trong Python — Mẹo cho Max-heap

Module heapq chỉ cài min-heap. Để có max-heap, dùng mẹo nhân âm:

import heapq

# Min-heap
h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
heapq.heappush(h, 5)
heapq.heappop(h)        # 1 (nhỏ nhất)
h[0]                    # 3 (peek không pop)

# Max-heap idiom — nhân -1
h = []
heapq.heappush(h, -3)
heapq.heappush(h, -1)
heapq.heappush(h, -5)
-heapq.heappop(h)       # 5 (lớn nhất, đảo dấu khi đọc)

heapify từ list có sẵn

arr = [9, 5, 6, 2, 3]
heapq.heapify(arr)      # In-place, O(n)
arr[0]                  # 2 — phần tử nhỏ nhất sau heapify

1.3 Operations và complexity

Heap với tuple — sort theo key custom

heapq.heappush(h, (priority, item))   # heap sort theo priority
heapq.heappush(h, (priority, idx, item))  # tiebreaker = idx khi priority bằng

1.4 Khi nào dùng Heap?

Heap vs Sort — khi nào ưu tiên cái nào?

• Sort: cần toàn bộ thứ tự, n nhỏ.
• Heap: chỉ cần K cực đoan, n lớn — đặc biệt khi stream (dữ liệu đến từng bước).

Sort O(n log n) toàn bộ; Heap O(n log K) chỉ cho K phần tử quan tâm — lợi rõ rệt khi K << n.

2.1 Pattern Top-K với Heap size K

Template chuẩn

def top_k_largest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)             # bỏ phần tử nhỏ nhất ngoài top-K
    return h                              # K phần tử lớn nhất, không sort

Time O(n log K), Space O(K).

2.2 Worked Example 1 — Kth Largest Element in an Array

Đề (LeetCode #215): Tìm phần tử lớn thứ k trong mảng (không khác nhau).

Approach 1 — Sort

def findKthLargest(nums, k):
    return sorted(nums)[-k]
# Time O(n log n)

Approach 2 — Min-heap size K (chuẩn)

def findKthLargest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h[0]                       # nhỏ nhất trong top-K = phần tử thứ k lớn nhất
# Time O(n log K)

Approach 3 — Quick Select (Tuần 8 review)

# Trung bình O(n), worst case O(n²) — partition-based

So sánh: Sort đơn giản nhất, Heap tốt nhất cho stream, Quick Select nhanh nhất trung bình.

2.3 Kth Largest — Trace tay (Heap approach)

nums = [3, 2, 1, 5, 6, 4], k = 2. Kỳ vọng: 5.

Trả h[0] = 5 ✓.

2.4 Worked Example 2 — Top K Frequent Elements (Heap revisit)

Đề (LeetCode #347): Top K phần tử xuất hiện nhiều nhất.

Tuần 3 đã làm với Bucket Sort O(n). Giờ thêm cách Heap O(n log K):

from collections import Counter
import heapq

def topKFrequent(nums, k):
    cnt = Counter(nums)
    return heapq.nlargest(k, cnt.keys(), key=cnt.get)

Tự cài thay vì nlargest

def topKFrequent(nums, k):
    cnt = Counter(nums)
    h = []
    for num, freq in cnt.items():
        heapq.heappush(h, (freq, num))      # min-heap theo freq
        if len(h) > k:
            heapq.heappop(h)
    return [num for freq, num in h]

So sánh 3 cách

• Sort: O(n log n)
• Heap O(n log K): tốt khi K << n
• Bucket Sort: O(n) — nhanh nhất nhưng cần biết miền giá trị

2.5 Worked Example 3 — K Closest Points to Origin

Đề (LeetCode #973): Mảng các điểm points[i] = [x, y]. Trả K điểm gần gốc toạ độ nhất.

Quan sát

"K nhỏ nhất" theo khoảng cách → dùng max-heap size K. Khi heap quá K, pop phần tử xa nhất.

def kClosest(points, k):
    h = []
    for x, y in points:
        d = x*x + y*y                     # bình phương khoảng cách (đủ để so sánh)
        heapq.heappush(h, (-d, x, y))     # nhân -1 để max-heap
        if len(h) > k:
            heapq.heappop(h)
    return [[x, y] for _, x, y in h]

Time O(n log K), Space O(K).

2.6 Worked Example 4 — Last Stone Weight

Đề (LeetCode #1046): Mảng stones. Mỗi vòng, chọn 2 viên nặng nhất: nếu bằng → cả hai biến mất; nếu khác → viên mới = hiệu. Trả về viên cuối còn lại (0 nếu hết).

Pattern: max-heap với simulation

def lastStoneWeight(stones):
    h = [-s for s in stones]              # max-heap idiom
    heapq.heapify(h)                      # O(n)
    while len(h) > 1:
        a = -heapq.heappop(h)             # nặng nhất
        b = -heapq.heappop(h)             # nặng thứ hai
        if a != b:
            heapq.heappush(h, -(a - b))
    return -h[0] if h else 0

Time O(n log n), Space O(n).

Knowledge Check — Top-K Patterns

3.1 Pattern K-way Merge

Tinh thần

Tại mỗi bước, lấy nhỏ nhất trong K đầu hiện tại, đẩy vào kết quả, đẩy đầu mới của nguồn đó vào heap.

Khi nào dùng?

• Merge K Sorted Lists / Arrays.
• Smallest range covering K lists.
• K Smallest Pairs, K Smallest Sums.
• External sort (merge nhiều file đã sort trên đĩa).

3.2 Worked Example 5 — Merge K Sorted Lists (Hard)

Đề (LeetCode #23, Hard): Cho k linked list đã sort. Merge thành 1 list sort.

import heapq
def mergeKLists(lists):
    h = []
    # Push (val, idx, node) — idx làm tiebreaker để tránh "< not supported"
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(h, (head.val, i, head))

    dummy = ListNode(0)
    tail = dummy
    while h:
        val, i, node = heapq.heappop(h)
        tail.next = node
        tail = tail.next
        if node.next:
            heapq.heappush(h, (node.next.val, i, node.next))
    return dummy.next

Time O(N log K) với N = tổng node, K = số list.

Phân tích

Heap tối đa K phần tử. Mỗi node được push 1 lần và pop 1 lần → tổng N × O(log K).

3.3 Merge K Sorted Lists — Trace

3 list: [1→4→5], [1→3→4], [2→6].

Hết heap → trả output. Heap không vượt 3 phần tử.

3.4 Worked Example 6 — Find K Smallest Pairs

Đề (LeetCode #373): Hai mảng sort nums1, nums2, số k. Trả K cặp (u, v) có tổng nhỏ nhất.

Quan sát

Tổng số cặp = n × m, có thể rất lớn. Brute force: tạo mọi cặp + sort → O(nm log(nm)). Cần tốt hơn.

Min-heap với "expand" thông minh

def kSmallestPairs(nums1, nums2, k):
    if not nums1 or not nums2: return []
    h = []
    # Khởi tạo: ghép nums1[i] với nums2[0], i ∈ [0, min(k, len(nums1)))
    for i in range(min(k, len(nums1))):
        heapq.heappush(h, (nums1[i] + nums2[0], i, 0))

    res = []
    while h and len(res) < k:
        s, i, j = heapq.heappop(h)
        res.append([nums1[i], nums2[j]])
        if j + 1 < len(nums2):
            heapq.heappush(h, (nums1[i] + nums2[j+1], i, j+1))
    return res

Time O(K log K), Space O(K).

Knowledge Check — K-way Merge

4.1 Pattern Two Heaps

Tính chất

• Median = top của heap lớn hơn (khi tổng lẻ) hoặc trung bình hai top (khi tổng chẵn).
• Add: O(log n). Find median: O(1).

Pattern này áp dụng cho mọi bài "duy trì median động khi dữ liệu đến từng bước".

4.2 Worked Example 7 — Find Median from Data Stream (Hard)

Đề (LeetCode #295, Hard): Cài data structure hỗ trợ:

• addNum(num) — thêm số.
• findMedian() — trả median của các số đã thêm.

import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []                            # max-heap (nhân -1)
        self.hi = []                            # min-heap

    def addNum(self, num):
        # Bước 1: đẩy vào lo, sau đó lấy top lo đẩy sang hi
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        # Bước 2: nếu hi lớn hơn → cân bằng lại
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

addNum O(log n), findMedian O(1).

4.3 Median Stream — Trace tay

Stream: 1, 2, 3, 4, 5

5.1 BST Operations — Tóm tắt

Worst case = O(n) khi cây bị skewed (mỗi node chỉ có 1 con). Balanced BST (AVL, Red-Black) đảm bảo O(log n) — nhưng LeetCode ít khi yêu cầu cài.

Search và Insert — đơn giản

def search(root, target):
    if not root or root.val == target: return root
    if target < root.val:
        return search(root.left, target)
    return search(root.right, target)

Đệ quy theo nhánh duy nhất → O(h) với h = chiều cao cây.

5.2 Worked Example 8 — Kth Smallest in BST

Đề (LeetCode #230): Trả phần tử nhỏ thứ k trong BST.

Quan sát then chốt

Inorder của BST cho dãy sort tăng dần (Tuần 8). Phần tử thứ k của inorder = đáp án.

Approach 1 — Inorder đầy đủ

def kthSmallest(root, k):
    res = []
    def inorder(node):
        if not node: return
        inorder(node.left)
        res.append(node.val)
        inorder(node.right)
    inorder(root)
    return res[k - 1]
# Time O(n), Space O(n) — không tận dụng "dừng sớm"

Approach 2 — Inorder iterative với early stop

def kthSmallest(root, k):
    stack = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        k -= 1
        if k == 0: return cur.val
        cur = cur.right
# Time O(h + k), Space O(h)

5.3 Worked Example 9 — Insert into BST

Đề (LeetCode #701): Thêm node giá trị val vào BST. Trả root cây mới.

def insertIntoBST(root, val):
    if not root: return TreeNode(val)            # đến vị trí trống → tạo node
    if val < root.val:
        root.left = insertIntoBST(root.left, val)
    else:
        root.right = insertIntoBST(root.right, val)
    return root

Time O(h), Space O(h).

Phân tích leap of faith

Tin rằng insertIntoBST(root.left, val) trả về cây con trái với val đã chèn. Gán lại root.left = ... để cây cha "biết" thay đổi. Đây là pattern "trả về node đã sửa, gán lại" — xuất hiện ở Insert/Delete BST.

5.4 Worked Example 10 — Delete from BST

Đề (LeetCode #450): Xoá node có key trong BST. Trả root cây mới.

Ba case quan trọng khi xoá

1. Node là leaf: xoá thẳng (return None lên).
2. Node có 1 con: thay node bằng con đó.
3. Node có 2 con: thay bằng inorder successor (nhỏ nhất bên phải) hoặc inorder predecessor (lớn nhất bên trái), rồi đệ quy xoá successor đó.

def deleteNode(root, key):
    if not root: return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:                                          # node cần xoá
        if not root.left: return root.right        # case 1+2
        if not root.right: return root.left        # case 1+2
        # Case 3: tìm successor
        succ = root.right
        while succ.left: succ = succ.left
        root.val = succ.val                        # copy giá trị
        root.right = deleteNode(root.right, succ.val)   # xoá successor
    return root

Time O(h), Space O(h).

Knowledge Check — Two Heaps & BST

6.0 Decision Tree — Khi nào dùng Heap?

Quy tắc chọn nhanh

Tự hỏi: "Mỗi bước có cần biết phần tử cực đoan của tập đã thấy không?" Có → Heap.

Tổng kết Tuần 9

Đã học

• Heap fundamentals: min/max heap, heapify O(n), idiom max-heap qua nhân -1.
• Top-K Pattern: quy tắc đảo ngược (min-heap cho top-K largest); template chuẩn O(n log K).
• K-way Merge: heap chứa K "đầu hiện tại", expand frontier; mẹo idx tiebreaker.
• Two Heaps: max-heap + min-heap cân bằng cho median stream — bài "boss" #295.
• BST Operations: insert/delete với "trả về node đã sửa, gán lại"; 3 case của delete; Kth Smallest qua inorder + early stop.
• So sánh Heap vs Sort vs Bucket Sort: chọn theo K vs n và miền giá trị.

Bài về nhà (12 bài)

1. LeetCode #215 — Kth Largest Element in an Array (3 approach)
2. LeetCode #347 — Top K Frequent Elements (heap approach)
3. LeetCode #973 — K Closest Points to Origin
4. LeetCode #1046 — Last Stone Weight
5. LeetCode #23 — Merge K Sorted Lists (Hard)
6. LeetCode #373 — Find K Pairs with Smallest Sums
7. LeetCode #295 — Find Median from Data Stream (Hard, boss)
8. LeetCode #621 — Task Scheduler (max-heap simulation)
9. LeetCode #230 — Kth Smallest Element in a BST
10. LeetCode #701 — Insert into a Binary Search Tree
11. LeetCode #450 — Delete Node in a BST
12. LeetCode #703 — Kth Largest Element in a Stream (online)