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

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 4 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), code heapsort in-place Java, và nền tảng để hiểu Dijkstra (Module 5 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 cùng 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 cuoi, fill tu trai

Heap property (min-heap): với mọi node i, value(parent(i)) nhỏ hơn hoặc bằng value(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):

Array: [1, 3, 2, 7, 5, 4]
Index:  0  1  2  3  4  5

Tree mapping (0-indexed):
  parent(i) = (i - 1) / 2
  left(i)   = 2 * i + 1
  right(i)  = 2 * i + 2

Kiem tra: parent(3) = (3-1)/2 = 1  -> arr[1] = 3  (cha cua 7)
          left(1)   = 2*1+1   = 3  -> arr[3] = 7  (con trai cua 3)
          right(1)  = 2*1+2   = 4  -> arr[4] = 5  (con phai cua 3)

         1   (index 0)
        / \
       3   2  (index 1, 2)
      / \ /
     7  5 4   (index 3, 4, 5)

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.

// Min-heap sift-up: restore heap property upward from index i
private void siftUp(int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] < heap[parent]) {
            int tmp = heap[i]; heap[i] = heap[parent]; heap[parent] = tmp;
            i = parent;
        } else {
            break;  // heap property restored -- stop early
        }
    }
}

Insert = append cuối + sift-up:

public void insert(int value) {
    heap[size] = value;
    siftUp(size);
    size++;
}

Độ phức tạp: O(log n) — sift-up đi tối đa từ leaf lên root, chiều cao cây là log n.

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.

// Min-heap sift-down: restore heap property downward from index i
private void siftDown(int i, int size) {
    while (true) {
        int left    = 2 * i + 1;
        int right   = 2 * i + 2;
        int smallest = i;

        if (left < size && heap[left] < heap[smallest])   smallest = left;
        if (right < size && heap[right] < heap[smallest]) smallest = right;

        if (smallest == i) break;  // both children >= i, heap property holds

        int tmp = heap[i]; heap[i] = heap[smallest]; heap[smallest] = tmp;
        i = smallest;
    }
}

Extract-min = swap root với last + size-- + sift-down:

public int extractMin() {
    int min = heap[0];
    heap[0] = heap[--size];   // move last element to root
    siftDown(0, size);        // restore heap property from root
    return min;
}

Độ phức tạp: O(log n) — sift-down đi tối đa từ root xuống leaf.

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 insertions, each O(log n) -> O(n log n) total
for (int x : arr) {
    insert(x);  // append + sift-up
}

Tổng: n × O(log n) = O(n log n).

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.

public void buildHeap(int[] arr) {
    this.heap = arr;
    this.size = arr.length;
    // Start from last non-leaf node and sift-down toward root
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        siftDown(i, size);
    }
}

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 ở height h tốn tối đa O(h) bước. Trong cây n node:

• Số node ở height h tối đa bằng ceil(n / 2^(h+1))
• Height 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 (height 0) — sift-down tốn 0 bước. Một phần tư node ở height 1 — sift-down tốn tối đa 1 bước. Một phần tám ở height 2 — tối đa 2 bước. Tổng hội tụ về O(n) vì các node ở height cao (tốn nhiều công) số lượng ít theo hàm mũ.

Java new 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.

public static void heapSort(int[] arr) {
    int n = arr.length;

    // Phase 1: build max-heap in-place
    // (sort ascending needs max-heap so largest ends up at back)
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDownMax(arr, i, n);
    }

    // Phase 2: extract max repeatedly, place at end of array
    for (int i = n - 1; i > 0; i--) {
        // arr[0] = current max; swap to position i (its final sorted position)
        int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
        // shrink heap by 1 (arr[i] is now sorted), restore max-heap for arr[0..i-1]
        siftDownMax(arr, 0, i);
    }
}

private static void siftDownMax(int[] arr, int i, int size) {
    while (true) {
        int left    = 2 * i + 1;
        int right   = 2 * i + 2;
        int largest = i;

        if (left < size && arr[left] > arr[largest])   largest = left;
        if (right < size && arr[right] > arr[largest]) largest = right;

        if (largest == i) break;

        int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
        i = largest;
    }
}

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

Phase 1 -- build max-heap:
  Start: [3, 1, 4, 1, 5, 9, 2, 6]
  After buildHeap: [9, 6, 4, 1, 5, 3, 2, 1]  (max-heap: 9 at root)

Phase 2 -- extract max repeatedly:
  i=7: swap arr[0]=9 with arr[7]=1 -> [1, 6, 4, 1, 5, 3, 2, 9]
       siftDown(0, 7)               -> [6, 5, 4, 1, 1, 3, 2, | 9]
  i=6: swap arr[0]=6 with arr[6]=2 -> [2, 5, 4, 1, 1, 3, 6, | 9]
       siftDown(0, 6)               -> [5, 2, 4, 1, 1, 3, | 6, 9]
  ... (continue)
  Final: [1, 1, 2, 3, 4, 5, 6, 9]  (sorted ascending)

5.1 Properties của heapsort

• In-place: O(1) extra space — sort ngay trên array gốc. Phase 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.
• Not 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)

// SLOW: n * O(log n) = O(n log n)
List<Integer> data = List.of(5, 3, 8, 1, 9, 2, 7);
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : data) {
    pq.add(x);  // each add() is sift-up O(log n)
}

// FAST: O(n) -- constructor calls heapify() internally
PriorityQueue<Integer> pq2 = new PriorityQueue<>(data);

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. Đo bằng JMH để thấy rõ.

Pitfall 2 — PriorityQueue.iterator() không sorted

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 3, 8, 1));

// WRONG: for-each iterates backing array in heap order (NOT sorted)
for (int x : pq) {
    System.out.print(x + " ");  // may print: 1 3 8 5 -- heap order
}

// CORRECT: poll() repeatedly gives sorted order
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");  // prints: 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:

// Conceptual indexed PQ (simplified)
// Maintains: heap array + positionOf map (key -> heap index)
class IndexedMinHeap {
    private int[] heap;          // heap[i] = key value
    private int[] positionOf;    // positionOf[key] = current index in heap
    private int size;

    // After any swap, update positionOf for both swapped keys
    private void swap(int i, int j) {
        positionOf[heap[i]] = j;
        positionOf[heap[j]] = i;
        int tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp;
    }

    // decrease-key: update priority and sift-up from current position
    public void decreaseKey(int key, int newPriority) {
        int idx = positionOf[key];
        heap[idx] = newPriority;   // update value
        siftUp(idx);               // may need to bubble up
    }
}

decrease-key quan trọng cho Dijkstra shortest path: khi tìm đường ngắn hơn đến vertex 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ự).

Java không có built-in Indexed PQ. Alternatives:

• Implement IndexedMinHeap thủ công (25-30 dòng).
• Dùng TreeMap<Integer, Integer> (priority → key) với re-insert: O(log n) nhưng overhead constant lớn hơn.

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

9. Applied to tech

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. Source: PriorityQueue.java trong OpenJDK. Cross-link: Module 2 lesson 06.

Dijkstra shortest path (Module 5 lesson 05) — dùng min-heap để pick vertex 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 5 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, 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, 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, not 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.
• new 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)