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)

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.

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).

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)