Chương 15 - Heap

Heap (Priority Queue) trả lời nhanh câu hỏi “phần tử lớn/nhỏ nhất bây giờ là gì?”. Hai thao tác cốt lõi push và pop đều O(log n). Heap giải gọn các bài: top-k, median trên data stream, merge k lists, scheduling. Pattern phổ biến nhất: heap kích thước k để duy trì k phần tử tốt nhất.

Mục tiêu chương

Sau chương này, bạn sẽ:

• Pattern heap size k → top k phần tử O(n log k).
• Pattern 2 heap (low max-heap + high min-heap) cho median.
• K-way merge với heap chứa head mỗi list.
• Biết max-heap trong Python = push -x (vì heapq là min-heap).

Khi nào dùng pattern này?

• Cần lấy top k liên tục từ stream (Top K, Kth Largest).
• Cần lấy min/max động khi insert/delete (Median, Sliding Window Max - nhưng cái sau dùng monotonic deque, Chương 18).
• K-way merge (gộp k list đã sort).
• Greedy với priority (Task Scheduler, Reorganize String, Meeting Rooms).

Python heapq chỉ có min-heap. Muốn max-heap → push -x.

Template code

import heapq

# 1) Min-heap cơ bản
heap: list[int] = []
heapq.heappush(heap, x)
top = heap[0]              # peek (không pop)
val = heapq.heappop(heap)

# 2) Max-heap bằng cách negate
heapq.heappush(heap, -x)
val = -heapq.heappop(heap)

# 3) K phần tử nhỏ nhất / lớn nhất từ list
smallest_k = heapq.nsmallest(k, arr)        # O(n log k)
largest_k = heapq.nlargest(k, arr)

# 4) Heapify O(n) - nhanh hơn n lần push
heapq.heapify(arr)

# 5) Heap với key tuỳ ý - push tuple (priority, payload)
heapq.heappush(heap, (priority, payload))

Bài tự luyện cuối chương

• LC 378 - Kth Smallest Element in a Sorted Matrix
• LC 451 - Sort Characters By Frequency
• LC 502 - IPO
• LC 767 - Reorganize String
• LC 1046 - Last Stone Weight
• LC 1167 - Minimum Cost to Connect Sticks

---

15.1 Kth Largest Element in an Array (LC 215)

Đề bài

Cho mảng nums và số k. Trả về phần tử lớn thứ k (1-indexed, theo thứ tự giảm dần). Có duplicate.

Ví dụ

Input:  nums = [3, 2, 1, 5, 6, 4], k = 2     → 5
Input:  nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 → 4

Ràng buộc

• 1 <= k <= len(nums) <= 10^5
• -10^4 <= nums[i] <= 10^4

Clarifying questions

• k > len(nums)? → Theo đề: 1 ≤ k ≤ len.
• Duplicate? → Có (Kth largest tính cả duplicate).

Hướng tiếp cận

Cách 1 - Sort, O(n log n). sorted(nums)[-k]. Đơn giản nhất.

Cách 2 - Min-heap kích thước k, O(n log k).

Duyệt mảng, đẩy vào heap. Khi heap > k → pop. Cuối cùng heap[0] là Kth largest.

Cách 3 - Quickselect, O(n) trung bình.

Variant của quicksort: partition quanh pivot, recurse chỉ vào nửa chứa Kth.

Code Python 3

import heapq
from typing import List

class Solution:
    """Cách 2 - heap kích thước k."""

    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap: list[int] = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]


class SolutionQS:
    """Cách 3 - quickselect, O(n) trung bình."""

    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Kth largest = (n-k)-th smallest (0-indexed).
        target = len(nums) - k

        def partition(lo: int, hi: int) -> int:
            pivot = nums[hi]
            store = lo
            for i in range(lo, hi):
                if nums[i] < pivot:
                    nums[store], nums[i] = nums[i], nums[store]
                    store += 1
            nums[store], nums[hi] = nums[hi], nums[store]
            return store

        lo, hi = 0, len(nums) - 1
        while True:
            p = partition(lo, hi)
            if p == target:
                return nums[p]
            elif p < target:
                lo = p + 1
            else:
                hi = p - 1

Phân tích độ phức tạp

Cách	Time	Space
Sort	O(n log n)	O(1)
Heap size k	O(n log k)	O(k)
Quickselect	O(n) avg, O(n²) worst	O(1)

Bình luận

• Trong phỏng vấn: trình bày heap size k trước (gọn và hiệu quả khi k nhỏ), sau đó nhắc đến quickselect nếu interviewer hỏi “có cách O(n) không?”.
• Quickselect worst case xảy ra khi pivot luôn xấu - có thể tránh bằng random pivot.

Bài tự luyện liên quan

• LC 347 - Top K Frequent Elements (Chương 6).
• LC 973 - K Closest Points to Origin (bài 15.4).
• LC 703 - Kth Largest Element in a Stream.

---

15.2 Top K Frequent Words (LC 692)

Đề bài

Cho mảng words và số k. Trả về k từ thường gặp nhất. Nếu hoà tần suất, từ nào lexicographically smaller ưu tiên.

Ví dụ

Input:  words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Giải thích: "i" và "love" cùng tần suất 2. "i" < "love" trong từ điển.

Input:  k = 4
Output: ["the", "is", "sunny", "day"]   (tie → sort lex)

Ràng buộc

• 1 <= len(words) <= 500
• 1 <= len(words[i]) <= 10

Clarifying questions

• Tie freq + lex bằng nhau? → Lex thì luôn phân biệt (string distinct).

Hướng tiếp cận

Mấu chốt: comparator tie-break - tần suất cao hơn ưu tiên, nếu hoà thì từ lex nhỏ hơn ưu tiên.

Cách 1 - Sort, O(n log n). sorted(cnt.keys(), key=lambda w: (-cnt[w], w))[:k].

Cách 2 - Min-heap kích thước k, O(n log k).

Heap chứa tuple (freq, word). Vì heap min, ta muốn: - Tần suất thấp ở top (pop trước) → push thẳng freq. - Hoà → từ lex lớn hơn ở top (pop trước) → push word.

Trick: với từng tuple, ta dùng (-freq, word) rồi sort… không, dùng custom wrapper cũng được. Cách 1 đơn giản hơn nhiều.

Code Python 3

import heapq
from collections import Counter
from typing import List

class Solution:
    """Cách 1 - sort. Sạch nhất cho bài này."""

    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        cnt = Counter(words)
        return sorted(cnt.keys(), key=lambda w: (-cnt[w], w))[:k]


class SolutionHeap:
    """Cách 2 - min-heap kích thước k."""

    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        cnt = Counter(words)
        # Trong min-heap, muốn pop ra cái "thua kém" trước.
        # "Thua kém" = freq thấp hơn HOẶC (freq bằng + word lex lớn hơn).
        # Dùng tuple (freq, -word_chars) thì không tiện vì word là string.
        # Cách: dùng wrapper class.

        class Wrap:
            __slots__ = ("freq", "word")
            def __init__(self, f, w): self.freq, self.word = f, w
            def __lt__(self, other):
                if self.freq != other.freq:
                    return self.freq < other.freq      # min-heap → freq nhỏ ở top
                return self.word > other.word          # tie → word lex LỚN ở top
            def __eq__(self, other):
                return (self.freq, self.word) == (other.freq, other.word)

        heap: list[Wrap] = []
        for w, f in cnt.items():
            heapq.heappush(heap, Wrap(f, w))
            if len(heap) > k:
                heapq.heappop(heap)
        # Pop ra → ngược lại để có thứ tự đúng.
        return [heapq.heappop(heap).word for _ in range(k)][::-1]

Phân tích độ phức tạp

• Sort: O(n log n). Heap: O(n log k).

Bình luận

• Tại sao sort thắng heap ở bài này về sự rõ ràng? Comparator tie-break trên string khó express ngắn gọn trong heap (vì heapq dùng __lt__ mặc định, không cho key=).
• Pattern wrapper với __lt__ tuỳ biến rất hữu ích - dùng được cho mọi trường hợp comparator phức tạp trên heap.

Bài tự luyện liên quan

• LC 347 - Top K Frequent Elements.
• LC 451 - Sort Characters By Frequency.

---

15.3 Find Median from Data Stream (LC 295)

Đề bài

Thiết kế class: - addNum(num): thêm num vào data stream. - findMedian(): trả về median hiện tại.

Median của n số: phần tử giữa (sorted), hoặc trung bình 2 phần tử giữa nếu n chẵn.

Ví dụ

Input (LC-style operation arrays):
  ops  = ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
  args = [[],             [1],      [2],      [],           [3],      []]

Output: [null, null, null, 1.5, null, 2.0]

Giải thích:
  MedianFinder()    → khởi tạo, null
  addNum(1)         → null;  stream = [1]
  addNum(2)         → null;  stream = [1, 2]
  findMedian()      → 1.5    (mean của 2 phần tử giữa)
  addNum(3)         → null;  stream = [1, 2, 3]
  findMedian()      → 2.0    (phần tử giữa của 3 số sorted)

Ràng buộc

• -10^5 <= num <= 10^5
• Tối đa 5·10^4 op

Clarifying questions

• Số phần tử lẻ? → Median = phần tử giữa. Chẵn → average.

Hướng tiếp cận

Trick 2 heap: - low = max-heap chứa nửa nhỏ (dưới median). - high = min-heap chứa nửa lớn (trên median).

Invariant: - Mọi phần tử trong low ≤ mọi phần tử trong high. - len(low) == len(high) hoặc len(low) == len(high) + 1.

addNum: 1. Push vào low (max-heap → push -num). 2. Đẩy top của low sang high (rebalance). 3. Nếu len(high) > len(low) → đẩy top của high về lại low.

findMedian: - len(low) > len(high) → low[0] (negated). - Bằng nhau → trung bình của 2 top.

Hình minh hoạ với stream 1, 2, 3:

addNum(1):
  push low=-1. low=[-1]
  move -low[0]=1 to high. low=[], high=[1]
  len(high) > len(low) → move 1 back to low. low=[-1], high=[]

  median: low[0]=-(-1)=1.0

addNum(2):
  push -2 to low. low=[-1, -2] → heap-balanced [-2, -1] (max-heap → 2 on top)
  Hmm cần check: max-heap đơn giản, top = max = 2.
  move 2 to high. low=[-1], high=[2]
  len(high) <= len(low) OK.

  median: (low[0] + high[0]) / 2 = (1 + 2) / 2 = 1.5  ✓

addNum(3):
  push -3 to low. After push: low contains -1 and -3.
  Top of max-heap = 1 (smallest negated → 1).
  move 1 to high. low=[-3] (i.e., values {3}), high=[1, 2]
  Hmm, now high has 2 items, low has 1.
  Wait that's wrong invariant. Let me redo.

Thực ra trick đúng:

addNum(num):
  if not low or num <= -low[0]:
      heappush(low, -num)
  else:
      heappush(high, num)
  # rebalance: |len(low) - len(high)| <= 1, low >= high in size
  if len(low) > len(high) + 1:
      heappush(high, -heappop(low))
  elif len(high) > len(low):
      heappush(low, -heappop(high))

Code Python 3

import heapq

class MedianFinder:
    def __init__(self):
        self.low: list[int] = []   # max-heap (negated)
        self.high: list[int] = []  # min-heap

    def addNum(self, num: int) -> None:
        if not self.low or num <= -self.low[0]:
            heapq.heappush(self.low, -num)
        else:
            heapq.heappush(self.high, num)
        # Rebalance.
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self) -> float:
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

Phân tích độ phức tạp

• addNum: O(log n). findMedian: O(1).
• Bộ nhớ: O(n).

Bình luận

• Tại sao 2 heap? Median chia mảng làm 2 - 1 heap mỗi nửa cho O(1) access vào “ranh giới” giữa 2 nửa.
• Pattern 2 heap xuất hiện ở: LC 480 (Sliding Window Median), Kth Largest Stream với khoảng động.

Bài tự luyện liên quan

• LC 480 - Sliding Window Median.
• LC 1825 - Finding MK Average.
• LC 703 - Kth Largest Element in a Stream.

---

15.4 K Closest Points to Origin (LC 973)

Đề bài

Cho mảng points, mỗi điểm [x, y]. Trả về k điểm gần origin nhất (Euclidean distance).

Ví dụ

Input:  points = [[1,3], [-2,2]], k = 1
Output: [[-2, 2]]
Giải thích: dist²(1,3) = 10, dist²(-2,2) = 8.

Ràng buộc

• 1 <= k <= len(points) <= 10^4
• -10^4 <= x, y <= 10^4

Clarifying questions

• Points trùng (x,y)? → Có thể; cùng distance, lấy bất kỳ.

Hướng tiếp cận

Cách heap size k - O(n log k). Max-heap chứa k điểm gần nhất; khi vượt k, pop điểm xa nhất.

Lưu ý: dùng dist² thay vì sqrt(dist) - tránh float, giữ thứ tự không đổi.

Code Python 3

import heapq
from typing import List

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap: list[tuple[int, list[int]]] = []   # (-dist², point) - max-heap
        for p in points:
            d2 = p[0] ** 2 + p[1] ** 2
            heapq.heappush(heap, (-d2, p))
            if len(heap) > k:
                heapq.heappop(heap)
        return [p for _, p in heap]

Phân tích độ phức tạp

• Thời gian: O(n log k). Bộ nhớ: O(k).

Bình luận

• Quickselect cũng làm được O(n) trung bình (như bài 15.1), bằng cách partition theo dist².
• Bẫy float: so sánh sqrt(d²) thừa tính toán và mất chính xác - luôn so bằng d².

Bài tự luyện liên quan

• LC 215 - Kth Largest Element (bài 15.1).
• LC 658 - Find K Closest Elements (đã sort).

---

15.5 Merge k Sorted Lists (LC 23)

Đề bài

Input: lists: List[Optional[ListNode]] - mảng k head của k singly linked list đã sort tăng dần. Gộp tất cả thành 1 linked list sort và trả về head mới.

Ví dụ

Input:  lists = [1→4→5, 1→3→4, 2→6]
Output: 1→1→2→3→4→4→5→6

Ràng buộc

• 0 <= k <= 10^4
• 0 <= total nodes <= 10^4

Clarifying questions

• Một số list rỗng? → Skip khi push.
• Tất cả null? → Trả None.

Hướng tiếp cận

Cách 1 - Min-heap k-way merge, O(N log k).

Heap chứa (val, idx, node) của head mỗi list. Pop cái nhỏ nhất, push hàng tiếp theo từ cùng list. Lặp đến hết.

idx là tiebreaker - Python không so sánh ListNode được khi val bằng.

Cách 2 - Merge từng cặp (Divide & Conquer), O(N log k).

Mergesort kiểu tournament: ghép cặp lists rồi merge, lặp lại. Cùng độ phức tạp.

Code Python 3

import heapq
from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next


class Solution:
    """Cách 1 - min-heap k-way merge."""

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap: list[tuple[int, int, ListNode]] = []
        for i, head in enumerate(lists):
            if head:
                heapq.heappush(heap, (head.val, i, head))

        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

Phân tích độ phức tạp

• Thời gian: O(N log k) với N = tổng số node.
• Bộ nhớ: O(k) cho heap.

Bình luận

• Cách divide & conquer lý tưởng khi k rất nhỏ và muốn tránh dependency trên heap.
• Bẫy: quên idx tiebreaker → TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' khi val trùng.

Bài tự luyện liên quan

• LC 21 - Merge Two Sorted Lists.
• LC 264 - Ugly Number II.
• LC 632 - Smallest Range Covering Elements from K Lists.

---

15.6 Task Scheduler (LC 621)

Đề bài

Cho mảng tasks (chữ cái A-Z) và số n. Mỗi đơn vị thời gian thực hiện 1 task hoặc idle. 2 task giống nhau phải cách nhau ít nhất n đơn vị. Trả về số đơn vị thời gian tối thiểu để hoàn thành tất cả.

Ví dụ

Input:  tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Lịch:   A → B → idle → A → B → idle → A → B

Ràng buộc

• 1 <= len(tasks) <= 10^4
• tasks[i] ∈ ‘A’-‘Z’
• 0 <= n <= 100

Clarifying questions

• n = 0? → Vẫn dùng được; LC tasks luôn có ít nhất 1.
• n rất lớn (n > len(tasks))? → Vẫn return được kết quả

  = len(tasks).

Hướng tiếp cận

Cách 1 - Greedy + max-heap, O(N log 26).

Mỗi tick: - Lấy task có freq cao nhất (heap top). Decrement freq, đẩy vào “cooldown queue” (end_time, freq).

• Khi cooldown_queue.front().end_time <= now → pop và đẩy lại vào heap.

Cách 2 - Công thức trực tiếp, O(N).

Cho f_max = freq cao nhất, count_max = số task có freq này. Đáp án = max(n_total, (f_max - 1) * (n + 1) + count_max).

Trực giác: Task có freq cao nhất tạo ra f_max - 1 khoảng có độ dài n+1, cộng count_max cuối ở “row cuối”.

Code Python 3

from collections import Counter
from typing import List

class Solution:
    """Cách 2 - công thức O(N)."""

    def leastInterval(self, tasks: List[str], n: int) -> int:
        cnt = Counter(tasks)
        f_max = max(cnt.values())
        count_max = sum(1 for v in cnt.values() if v == f_max)
        slots = (f_max - 1) * (n + 1) + count_max
        return max(slots, len(tasks))


import heapq
from collections import deque

class SolutionHeap:
    """Cách 1 - heap + cooldown queue."""

    def leastInterval(self, tasks: List[str], n: int) -> int:
        heap = [-c for c in Counter(tasks).values()]   # max-heap (negated)
        heapq.heapify(heap)
        cooldown: deque[tuple[int, int]] = deque()     # (available_time, neg_count)
        time = 0
        while heap or cooldown:
            time += 1
            if heap:
                neg = heapq.heappop(heap) + 1          # giảm freq 1 đơn vị
                if neg < 0:
                    cooldown.append((time + n, neg))
            if cooldown and cooldown[0][0] == time:
                _, neg = cooldown.popleft()
                heapq.heappush(heap, neg)
        return time

Phân tích độ phức tạp

• Công thức: O(N). Heap: O(N log 26).

Bình luận

• Tại sao công thức work? Sắp task theo lưới (f_max - 1) hàng × (n + 1) cột, ô cuối có thể có nhiều task share freq cao nhất.
• Pattern heap + cooldown sẽ tái xuất ở các bài “Reorganize String” (LC 767), “Rearrange String K Distance Apart” (LC 358).

Bài tự luyện liên quan

• LC 767 - Reorganize String.
• LC 358 - Rearrange String K Distance Apart.
• LC 1834 - Single-Threaded CPU.

Tóm tắt chương & Quyết định

Heap vs Sort vs Quickselect

Yêu cầu	Heap O(n log k)	Sort O(n log n)	Quickselect O(n) avg
Top-k khi n lớn, k nhỏ	✅ Tốt nhất	OK	✅ Khi không cần thứ tự
Cần k phần tử đã sắp	✅	✅	Cần sort thêm sau
Streaming (data đến từng phần)	✅	❌	❌
Đảm bảo worst-case	✅	✅	❌ (worst O(n²))
Interview preference	Mặc định, dễ giải thích	Khi n nhỏ	Khi push “linear time”

Median Finder invariant

max_heap (lo)      min_heap (hi)
  …,3,5,7,8  ←     ←  9,10,12,…
top = 8                top = 9

• |len(lo) - len(hi)| ≤ 1, mọi phần tử lo ≤ mọi phần tử hi.
• Add: push tạm sang heap kia rồi balance.
• Median = top heap lớn hơn, hoặc trung bình 2 top khi bằng size.

Task Scheduler 2 cách

• Heap simulation: push count vào max-heap; mỗi cycle n+1 lấy ra nhiều nhất n+1 task khác nhau.
• Counting formula: max((max_count - 1) * (n + 1) + ties, total_tasks). Đẹp & nhanh hơn nhưng cần chứng minh.

Top K Frequent Words tie-break

Sort theo (-freq, word): tần số giảm dần, từ điển tăng dần.

---