Binary heap & Heapsort — Build-heap O(n) và priority queue backbone

TL;DR: Binary heap là complete binary tree lưu trong array — không cần pointer, parent ở index (i-1)/2, left child ở 2i+1, right child ở 2i+2 (0-indexed). Hai operation cốt lõi: sift-up (dùng cho insert, O(log n)) và sift-down (dùng cho extract-min và build-heap, O(log n)). Build-heap từ n phần tử tùy ý chạy O(n) — không phải O(n log n) như nhiều người nghĩ — vì phần nửa số node là leaf tốn 0 công, tổng hội tụ qua geometric series. Heapsort = build max-heap O(n) + n lần extract-max O(log n) = O(n log n) always, in-place, không stable. Trong thực tế thua Quick sort về cache locality nhưng thắng khi cần O(1) space và O(n log n) guaranteed.

Thuật toán Căn bản — Module 2 lesson 06 đã dùng PriorityQueue để giải top-K và Dijkstra qua API: offer, poll, peek. Nhưng bài đó dừng lại ở câu chú thích: "Chi tiết sift-up, sift-down, và buildHeap O(n) để Module 2 lesson 05 phân tích."

Đây là bài đó.

Câu hỏi cốt lõi: new PriorityQueue<>(collection) nhận một Collection n phần tử và sắp xếp thành heap — nó mất bao nhiêu thời gian? Nhiều junior trả lời "O(n log n)" vì nghĩ là n lần insert, mỗi lần O(log n). Đáp án đúng là O(n) — và chứng minh tại sao lại là một trong những insight đẹp nhất trong phân tích thuật toán.

Bài này dạy heap structure, sift-up / sift-down, chứng minh build-heap O(n), pseudocode heapsort in-place, và nền tảng để hiểu Dijkstra (Module 3 lesson 05) cũng như indexed PQ khi cần decrease-key.

1. Analogy — Tháp ưu tiên một chiều

Hình dung một tháp đèn tín hiệu xếp tầng: mỗi ô là một task với độ ưu tiên. Quy tắc duy nhất: ô trên luôn có ưu tiên cao hơn hoặc bằng ô dưới. Tháp luôn "đầy từ trái" — không bao giờ có lỗ trống ở giữa.

Khi thêm task mới: đặt vào ô cuối cùng còn trống (tầng thấp nhất, trái nhất), rồi "đẩy lên" cho đến khi quy tắc thỏa mãn. Khi lấy task ưu tiên cao nhất: lấy đỉnh tháp, đưa ô cuối lên thay, rồi "thả xuống" cho đến khi quy tắc thỏa mãn.

2. Cấu trúc binary heap

2.1 Complete binary tree và heap property

Complete binary tree: mọi level đầy trừ level cuối cùng. Level cuối fill từ trái sang phải — không bao giờ có lỗ trống bên trái mà có node bên phải.

Level 0:         1          -- root
Level 1:       3   2
Level 2:      7  5 4        -- level cuối, fill từ trái

Heap property (min-heap): với mọi node i, giá trị của parent(i) nhỏ hơn hoặc bằng giá trị của i. Root là phần tử nhỏ nhất toàn cây. Max-heap thì ngược lại.

2.2 Lưu trong array — index arithmetic

Vì complete binary tree không có lỗ trống, có thể lưu trực tiếp vào array mà không cần pointer. Dùng 0-indexed (chuẩn Java):

Mảng: [1, 3, 2, 7, 5, 4]
Index: 0  1  2  3  4  5

Ánh xạ cây (0-indexed):
  parent(i) = (i - 1) / 2
  left(i)   = 2 * i + 1
  right(i)  = 2 * i + 2

Kiểm tra: parent(3) = (3-1)/2 = 1  -> heap[1] = 3  (cha của 7)
          left(1)   = 2*1+1   = 3  -> heap[3] = 7  (con trái của 3)
          right(1)  = 2*1+2   = 4  -> heap[4] = 5  (con phải của 3)

graph TD
    N0["1 (index 0)"]
    N1["3 (index 1)"]
    N2["2 (index 2)"]
    N3["7 (index 3)"]
    N4["5 (index 4)"]
    N5["4 (index 5)"]

    N0 --> N1
    N0 --> N2
    N1 --> N3
    N1 --> N4
    N2 --> N5

Java PriorityQueue dùng 0-indexed. Một số giáo trình (CLRS) dùng 1-indexed để công thức gọn hơn: parent = i/2, left = 2i, right = 2i+1. Hai convention tương đương — chỉ cần nhất quán.

3. Sift-up và sift-down — hai operation cốt lõi

3.1 Sift-up (dùng cho insert)

Sau khi append element mới vào cuối array, heap property có thể bị vi phạm tại node mới đó (nó có thể nhỏ hơn parent). Sift-up sửa bằng cách đổi chỗ với parent liên tục cho đến khi tính chất được khôi phục.

SiftUp(heap, i):
    while i > 0:
        parent <- (i - 1) / 2
        if heap[i] < heap[parent]:           -- min-heap: node nhỏ hơn parent thì đẩy lên
            swap heap[i] và heap[parent]
            i <- parent
        else:
            break                            -- heap property đã thỏa mãn, dừng

Insert(heap, value):
    heap[size] <- value
    SiftUp(heap, size)
    size <- size + 1

Time: O(log n) Space: O(1)

3.2 Sift-down (dùng cho extract-min và build-heap)

Sau khi lấy root (minimum), đưa element cuối cùng lên làm root rồi giảm size. Root mới có thể lớn hơn một hoặc cả hai con — sift-down sửa bằng cách đổi chỗ với con nhỏ nhất liên tục cho đến khi tính chất được khôi phục.

SiftDown(heap, i, size):
    while true:
        left    <- 2 * i + 1
        right   <- 2 * i + 2
        smallest <- i

        if left < size và heap[left] < heap[smallest]:
            smallest <- left
        if right < size và heap[right] < heap[smallest]:
            smallest <- right

        if smallest = i: break              -- cả hai con >= i, heap property thỏa mãn

        swap heap[i] và heap[smallest]
        i <- smallest

ExtractMin(heap, size):
    min <- heap[0]
    size <- size - 1
    heap[0] <- heap[size]                  -- đưa phần tử cuối lên root
    SiftDown(heap, 0, size)                -- khôi phục heap property từ root
    return min

Time: O(log n) Space: O(1)

Thử ngẫmExtractMin đưa phần tử cuối lên root rồi sift-down; Insert thêm vào cuối rồi sift-up. Một thao tác replace(old, new) cần gộp cả hai bước đó — bạn làm sao để vẫn chỉ tốn một lần O(log n)?

4. Build-heap — O(n) không phải O(n log n)

Cho array n phần tử tùy ý, muốn biến thành min-heap. Có hai cách:

Cách naive: insert từng element vào heap rỗng, sift-up mỗi lần.

-- Naive: n lần insert, mỗi lần O(log n) -> O(n log n) tổng
for each x trong A:
    Insert(heap, x)    -- append + sift-up

Time: O(n log n) Space: O(1)

Cách thông minh — build-heap O(n): sift-down từ node cuối cùng không phải leaf (index n/2 - 1) xuống root.

BuildHeap(A):
    size <- A.length
    -- bắt đầu từ node cuối không phải leaf, sift-down về phía root
    for i <- A.length/2 - 1 xuống 0:
        SiftDown(A, i, size)

Time: O(n) Space: O(1)

Tại sao bắt đầu từ n/2 - 1? Vì các node từ n/2 đến n-1 là leaf — chúng đã là heap hợp lệ (cây một node luôn thỏa mãn heap property). Chỉ cần sift-down các internal node.

4.1 Chứng minh O(n) — geometric series

Sift-down trên node ở chiều cao h tốn tối đa O(h) bước. Trong cây n node:

• Số node ở chiều cao h tối đa bằng ceil(n / 2^(h+1))
• Chiều cao tối đa của cây là floor(log n)

Tổng công việc:

T(n) = SUM_{h=0}^{floor(log n)} ceil(n / 2^(h+1)) × O(h)
     = O(n) × SUM_{h=0}^{infinity} h / 2^h
     = O(n) × 2          -- geometric series: SUM h/2^h = 2
     = O(n)

Intuition: phần nửa số node là leaf (chiều cao 0) — sift-down tốn 0 bước. Một phần tư node ở chiều cao 1 — sift-down tốn tối đa 1 bước. Một phần tám ở chiều cao 2 — tối đa 2 bước. Tổng hội tụ về O(n) vì các node ở chiều cao cao (tốn nhiều công) số lượng ít theo hàm mũ.

Java PriorityQueue(Collection) gọi heapify() trong PriorityQueue.java — đây là build-heap O(n), không phải n lần insert O(n log n). Đây là lý do khởi tạo từ Collection luôn nên dùng constructor thay vì loop add.

5. Heapsort — in-place O(n log n) guaranteed

Heapsort kết hợp build-heap với repeated extract-max để sort ascending in-place.

Trick: dùng max-heap để sort ascending. Extract max → đặt vào cuối array (vị trí đúng vĩnh viễn). Lặp lại cho phần còn lại.

HeapSort(A):
    n <- A.length

    -- Giai đoạn 1: build max-heap tại chỗ
    -- (sort tăng dần cần max-heap để phần tử lớn nhất đi về cuối)
    for i <- n/2 - 1 xuống 0:
        SiftDownMax(A, i, n)

    -- Giai đoạn 2: lặp lấy max, đặt về cuối
    for i <- n-1 xuống 1:
        -- A[0] = max hiện tại; swap về vị trí i (vị trí sorted cuối cùng)
        swap A[0] và A[i]
        -- thu nhỏ heap 1 đơn vị (A[i] đã sorted), khôi phục max-heap cho A[0..i-1]
        SiftDownMax(A, 0, i)

SiftDownMax(A, i, size):
    while true:
        left    <- 2 * i + 1
        right   <- 2 * i + 2
        largest <- i

        if left < size và A[left] > A[largest]:   largest <- left
        if right < size và A[right] > A[largest]: largest <- right

        if largest = i: break

        swap A[i] và A[largest]
        i <- largest

Time: O(n log n) Space: O(1)

Trace ví dụ: [3, 1, 4, 1, 5, 9, 2, 6]

Giai đoạn 1 -- build max-heap:
  Ban đầu: [3, 1, 4, 1, 5, 9, 2, 6]
  Sau buildHeap: [9, 6, 4, 1, 5, 3, 2, 1]  -- max-heap: 9 ở root

Giai đoạn 2 -- lấy max lặp lại:
  i=7: swap A[0]=9 với A[7]=1 -> [1, 6, 4, 1, 5, 3, 2, | 9]
       SiftDownMax(0, 7)       -> [6, 5, 4, 1, 1, 3, 2, | 9]
  i=6: swap A[0]=6 với A[6]=2 -> [2, 5, 4, 1, 1, 3, | 6, 9]
       SiftDownMax(0, 6)       -> [5, 2, 4, 1, 1, 3, | 6, 9]
  ... (tiếp tục)
  Cuối cùng: [1, 1, 2, 3, 4, 5, 6, 9]  -- sorted tăng dần

5.1 Properties của heapsort

• In-place: O(1) extra space — sort ngay trên array gốc. Giai đoạn 2 dùng phần cuối array làm "sorted section" thay cho output buffer.
• O(n log n) always: best = average = worst. Build-heap O(n) + n lần sift-down O(log n) mỗi lần = O(n log n) guaranteed.
• Không stable: swap trong sift-down có thể đổi chỗ các element bằng nhau.

Thử ngẫmheapsort in-place, O(n log n) luôn đúng ở mọi trường hợp — nhưng không stable. Sort một danh sách log theo timestamp rồi theo severity, heapsort ở bước hai còn giữ đúng thứ tự timestamp trong các severity bằng nhau không?

6. So sánh heapsort với Merge sort và Quick sort

Nhận xét thực tế: Heapsort có profile hấp dẫn trên giấy tờ (worst-case guaranteed, in-place) nhưng trong thực tế thường chậm hơn Quick sort 20-40% trên random data vì cache locality kém. Sift-down nhảy đến index 2i+1 — trên array lớn, khoảng cách đó vượt cache line. Quick sort partition truy cập memory gần tuần tự → prefetch-friendly.

Merge sort tuy dùng O(n) buffer nhưng access pattern rất sequential → cache-friendly, thường nhanh hơn Heapsort trên large dataset.

Heapsort thắng khi: embedded system không có heap memory cho buffer (không thể cấp phát O(n) extra), hoặc cần O(n log n) worst-case guarantee mà không dùng được O(n) extra memory.

7. Pitfall tổng hợp

Pitfall 1 — Loop add thay constructor: O(n log n) thay O(n)

-- CHẬM: n × O(log n) = O(n log n)
-- thêm từng phần tử vào PQ rỗng bằng vòng lặp
for each x trong data:
    PQ.add(x)    -- mỗi add() là sift-up O(log n)

-- NHANH: O(n) -- constructor gọi heapify() bên trong
-- PriorityQueue(data)  -- build-heap O(n)

Với n = 1 triệu, O(n) vs O(n log n) chênh lệch khoảng 20 lần trên large dataset.

Pitfall 2 — PriorityQueue iterator không trả về sorted order

-- WRONG: for-each duyệt backing array theo heap order (KHÔNG sorted)
-- for each x trong PQ:
--     print x   -- có thể in: 1 3 8 5 -- heap order

-- CORRECT: poll() lặp lại cho sorted order
-- while PQ không rỗng:
--     print PQ.poll()   -- in: 1 3 5 8

iterator() của PriorityQueue duyệt backing array theo thứ tự index — đây là heap order, không phải sorted order. Cross-link: Module 2 lesson 06 pitfall 1 giải thích chi tiết cùng pattern này.

Pitfall 3 — Heapsort thường thua Quick sort trên random data dù cùng Big-O

Heapsort worst case O(n log n) nghe có vẻ tốt hơn Quick sort O(n²). Nhưng trên random data, Quick sort thường nhanh hơn Heapsort 20-40%. Lý do: sift-down nhảy đến index 2i+1 và 2i+2 — với array lớn, khoảng cách đó vượt cache line (64 bytes), gây cache miss nhiều. Quick sort partition scan từ trái qua phải → sequential access → CPU prefetch hoạt động hiệu quả. Cross-link: Module 1 lesson 04 (cache locality và memory hierarchy).

Thử ngẫmsift-down nhảy tới index 2i+1/2i+2 — bước nhảy đó vượt cache line 64 byte, gây cache miss. Với một heap chỉ vài chục phần tử vừa đủ một cache line, khoảng cách hiệu năng với Quick sort còn giữ nguyên không?

8. Indexed PQ — khi cần decrease-key

Standard PriorityQueue không hỗ trợ "cập nhật priority của element đã có trong heap" theo O(log n) — vì không biết element đó đang ở index nào trong backing array.

Indexed PQ giải quyết bằng cách thêm một map key → index:

-- Indexed MinHeap (rút gọn)
-- Duy trì: heap[] + positionOf[] (key -> index trong heap)

Swap(i, j):
    positionOf[heap[i]] <- j          -- cập nhật vị trí sau swap
    positionOf[heap[j]] <- i
    swap heap[i] và heap[j]

DecreaseKey(key, newPriority):
    idx <- positionOf[key]            -- tìm vị trí hiện tại của key
    heap[idx] <- newPriority          -- cập nhật giá trị
    SiftUp(idx)                       -- có thể cần đẩy lên

Time: O(log n) Space: O(n)

decrease-key quan trọng cho Dijkstra shortest path: khi tìm đường ngắn hơn đến đỉnh v, cần giảm distance của v trong PQ. Standard PQ không support → phải re-insert với distance mới và chấp nhận stale entries (hoặc dùng Indexed PQ thực sự).

Cross-link: Module 3 lesson 05 sẽ implement Dijkstra đầy đủ với PQ strategy này.

9. Ứng dụng thực tế

Java PriorityQueue — backing structure là min-heap trong array. Constructor PriorityQueue(Collection) gọi heapify() là build-heap O(n). offer() gọi siftUp. poll() gọi siftDown. Cross-link: Module 2 lesson 06.

Dijkstra shortest path (Module 3 lesson 05) — dùng min-heap để pick đỉnh có distance estimate nhỏ nhất trong mỗi bước relax. Với graph thưa, complexity O((V+E) log V) — vượt trội so với O(V²) khi không dùng PQ. Cross-link: Module 3 lesson 05.

Linux CFS scheduler — vì sao dùng RB tree thay heap: Completely Fair Scheduler của Linux cần không chỉ extract-min (task tiếp theo cần chạy) mà còn range query (tất cả task trong khoảng virtual runtime nhất định để load balancing giữa các CPU). Heap chỉ hỗ trợ extract-min O(log n) — range query trên heap là O(n). RB tree hỗ trợ cả extract-min lẫn range query O(log n). Cross-link: Module 3 lesson 06 (RB tree).

Kafka producer batch — mỗi partition có một batch buffer với deadline flush (oldest unflushed message timestamp). Min-heap theo deadline đảm bảo partition chờ lâu nhất được flush trước — tránh starvation khi throughput cao.

10. Deep Dive

11. Tóm tắt

• Binary heap = complete binary tree lưu trong array — parent ở index (i-1)/2, left child ở 2i+1, right child ở 2i+2 (0-indexed). Cache-friendly vì không dùng pointer.
• Sift-up (O(log n)): dùng cho insert — đẩy element mới từ cuối lên đến khi heap property thỏa mãn.
• Sift-down (O(log n)): dùng cho extract-min và build-heap — thả element từ trên xuống, đổi chỗ với con nhỏ nhất.
• Build-heap O(n) — không phải O(n log n): sift-down từ node n/2-1 xuống root. Proof qua geometric series: phần nửa node là leaf tốn 0 công, tổng hội tụ về O(n).
• Heapsort = build max-heap O(n) + n lần extract-max O(log n) = O(n log n) always, in-place O(1) space, không stable.
• Heapsort thua Quick sort về cache locality: sift-down nhảy xa trong array → cache miss. Quick sort partition sequential → prefetch hiệu quả. Big-O giống nhau nhưng constant factor khác biệt.
• Indexed PQ thêm map key → index để hỗ trợ decrease-key O(log n) — cần thiết cho Dijkstra decrease-key, không có sẵn trong Java standard library.
• PriorityQueue(Collection) gọi build-heap O(n) — luôn dùng constructor thay loop add() khi có sẵn collection.

12. Tự kiểm tra

Bài tiếp theo: Counting / Radix / Bucket sort — non-comparison O(n)