Bài B-tree dạy một bài học bố trí: gói dữ liệu thành khối liền, thân thiện cache, thắng con trỏ rải rác. Heap nhị phân đẩy ý đó tới cực điểm — nó là một cây nhị phân không có một con trỏ nào, gói gọn trong một mảng phẳng. Nhưng bài này không dừng ở bố cục; nó đo hai câu hỏi mà hầu như ai cũng trả lời sai theo trí nhớ sách vở: dựng một heap tốn bao nhiêu, và một heap có "sắp xếp" dữ liệu cho bạn không. Câu thứ nhất dẫn tôi vào một cú hớ mà chỉ đồng hồ mới gỡ được.
Heap: cây nhị phân không con trỏ
Heap nhị phân là một cây nhị phân gói trong mảng: phần tử ở ô i có hai con ở ô 2i+1 và 2i+2, cha ở ô (i-1)/2. Không có node cấp phát riêng, không con trỏ — chỉ là số học trên chỉ số, và mọi phần tử nằm liền nhau trong bộ nhớ. Cây giữ đúng một bất biến: cha luôn nhỏ hơn hoặc bằng con (với min-heap). Hệ quả trực tiếp: ô gốc luôn là phần tử nhỏ nhất, nên đọc min tốn O(1).
Thêm một phần tử (push) thì đặt nó vào cuối mảng rồi "sift-up" — đổi chỗ với cha chừng nào nó còn nhỏ hơn cha — nhiều nhất là đi hết chiều cao cây, O(log n). Lấy min (pop) thì bỏ gốc, đưa phần tử cuối lên gốc, rồi "sift-down" cho tới đúng chỗ, cũng O(log n). Đo thực tế một cặp pop-rồi-push trên heap một triệu phần tử: 62 nano giây — đúng cỡ O(log n), nhanh và ổn định. Đây là ruột của hàng đợi ưu tiên: cấu trúc luôn trả ra phần tử ưu tiên nhất, dùng khắp nơi từ lập lịch, thuật toán Dijkstra, tới lấy top-k. Phần thú vị nằm ở câu hỏi tưởng đã biết: dựng cả cái heap từ n phần tử tốn bao nhiêu?
Đo: dựng heap tốn O(n) hay O(n log n)?
Có hai cách dựng một heap từ n phần tử. Cách một: chèn lần lượt — bắt đầu heap rỗng, push từng phần tử, mỗi push O(log n), nên tổng "phải là" O(n log n). Cách hai: heapify từ dưới lên — đặt cả n phần tử vào mảng rồi sift-down từ giữa mảng ngược về gốc, một thủ thuật cho tổng O(n). Trí nhớ sách vở của tôi rất rõ ràng: heapify O(n) thắng chèn-lần-lượt O(n log n), nhất là khi n lớn.
Tôi đo cả hai, ở nhiều kích thước, và nhìn vào số thao tác trên mỗi phần tử — con số này phẳng thì tổng là O(n), con số này tăng theo log n thì tổng là O(n log n):
n heapify chèn ngẫu nhiên chèn giảm dần (ca xấu) log2(n)
250 nghìn 1,9 thao tác 2,3 thao tác 16 thao tác 18
1 triệu 1,9 2,3 18 20
4 triệu 1,9 2,3 20 22
16 triệu 1,9 2,3 22 24
Cột heapify phẳng lì ở 1,9 — đúng O(n) như trí nhớ. Nhưng cột chèn-lần-lượt với dữ liệu ngẫu nhiên cũng phẳng, ở 2,3 thao tác mỗi phần tử — nó cũng là O(n), không hề tăng theo log n. Đây là chỗ tôi đã sai.
Một lần tôi đo hớ: "O(n log n) của chèn" là ca xấu, không phải điều bạn đo
Tôi vào bài chắc chắn sẽ thấy chèn-lần-lượt chậm hơn heapify theo bậc — đường cong dốc lên khi n lớn, vì "ai cũng biết" nó là O(n log n). Đo ra: với dữ liệu ngẫu nhiên, nó phẳng như heapify, chỉ chậm hơn một hằng số khoảng 35% (6,5 so với 4,9 nano giây mỗi phần tử). Hai con số phẳng ở nơi tôi chờ một con số dốc — theo kỷ luật của sê-ri, đó là dấu hiệu tôi đã hiểu nhầm đại lượng, và có một biến ẩn.
Biến ẩn là thứ tự dữ liệu vào. Phân tích O(n log n) của chèn-lần-lượt là trường hợp xấu nhất, không phải trường hợp trung bình. Khi bạn push một khóa ngẫu nhiên vào min-heap, nó gần như chắc chắn lớn hơn cha của nó, nên sift-up dừng lại gần như ngay lập tức — trung bình chỉ khoảng 2 phép so sánh, bất kể heap to cỡ nào. log n bước chỉ xảy ra khi phần tử mới phải trèo lên tận gốc, tức khi nó là min mới — và một khóa ngẫu nhiên hiếm khi là min mới. Để thấy cái O(n log n) sách vở nói, tôi phải cho vào ca xấu: chèn theo thứ tự giảm dần, khi ấy mỗi phần tử mới đều là min mới và phải trèo lên gốc. Cột đó lộ ngay: số thao tác mỗi phần tử leo từ 16 lên 22, bám sát log2(n) (18 → 24). Đó mới là O(n log n).
Bài học đo lường ở đây có hai tầng. Tầng một: big-O trường hợp xấu nhất không phải là thứ bạn đo trên dữ liệu bình thường — chèn-lần-lượt là O(n log n) trên giấy nhưng O(n) trong thực tế với đầu vào ngẫu nhiên, và nếu tôi tin con số xấu nhất một cách máy móc thì tôi đã tránh một cách dựng heap hoàn toàn ổn. Tầng hai, và đây mới là điểm thật của heapify: cái hơn của heapify không phải "luôn nhanh hơn trên dữ liệu ngẫu nhiên" (nó chỉ nhanh hơn một hằng số nhỏ), mà là nó O(n) bảo đảm bất kể thứ tự đầu vào. Chèn-lần-lượt phụ thuộc vào sự may mắn của dữ liệu; heapify thì không. Chọn heapify không phải vì nó nhanh hơn hôm nay, mà vì nó không bao giờ chậm hơn — đúng tinh thần "hỏi đúng/bền chưa trước khi khen nhanh".
Heap không sắp xếp dữ liệu
Cú hiểu nhầm thứ hai tôi muốn đo dứt điểm: nhiều người nghĩ một heap "sắp xếp" dữ liệu, hoặc một mảng heap là một mảng gần-sắp-xếp. Tôi heapify một triệu số ngẫu nhiên rồi kiểm: mảng đúng là một heap hợp lệ (mọi cha ≤ con), nhưng nếu đếm số cặp kề nhau a[i] ≤ a[i+1] thì chỉ 50% — đúng bằng một mảng ngẫu nhiên chưa đụng tới. Một mảng đã sắp xếp sẽ là 100%. Heap chỉ áp một thứ tự một phần: nó ghim phần tử nhỏ nhất lên gốc và giữ quan hệ cha-con, nhưng hai anh em, hay hai nhánh khác nhau, hoàn toàn không có thứ tự với nhau. Heap cho bạn cái min một cách rất rẻ, chứ không cho bạn toàn bộ thứ tự. Muốn thứ tự đầy đủ thì phải trả thêm — lấy min lặp lại n lần, và đó chính là heapsort, chuyện của một bài sau.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên rất thực dụng: khi bạn có sẵn cả mảng và cần biến nó thành hàng đợi ưu tiên, dùng heapify, đừng push từng phần tử. Không phải vì push từng cái sẽ chậm thảm hại — với dữ liệu ngẫu nhiên nó chỉ chậm hơn chút — mà vì heapify là một dòng lệnh O(n) chắc chắn, miễn nhiễm với thứ tự đầu vào xấu. Hầu hết thư viện chuẩn có sẵn thao tác này (make_heap của C++, heapify của Python); biết nó tồn tại là biết cách dựng đúng.
Hệ quả thứ hai: chọn heap khi bạn cần phần tử ưu tiên nhất lặp đi lặp lại, đừng chọn khi bạn cần thứ tự đầy đủ. Nếu bài toán là "luôn lấy ra cái nhỏ nhất hiện có, trong khi vẫn thêm phần tử mới" — lập lịch, Dijkstra, gộp nhiều luồng đã sắp, giữ top-k phần tử — heap là câu trả lời gần như hoàn hảo, vì nó không phí công sắp xếp những phần tử bạn có thể chẳng bao giờ chạm tới. Nhưng nếu bạn cần cả danh sách đã sắp, heap không cho bạn điều đó miễn phí; đừng nhầm "gốc là min" với "mảng đã sắp".
Hệ quả thứ ba là bài học đo lường mang theo. Con số cần nhớ: heapify dựng heap O(n) bất kể đầu vào (1,9 thao tác/phần tử, phẳng); chèn-lần-lượt là O(n log n) trên giấy nhưng đo ra O(n) với dữ liệu ngẫu nhiên (2,3 thao tác, phẳng), chỉ bung thành O(n log n) ở ca xấu giảm dần (16→22 thao tác theo log n); và heap không sắp xếp — mảng heap chỉ 50% cặp đúng thứ tự, nó cho min rẻ chứ không cho cả thứ tự. Khi lý thuyết nói "xấu nhất" mà đồng hồ nói "phẳng", đừng vội sửa đồng hồ — hãy hỏi dữ liệu của bạn có phải là ca xấu không.
Thử ba mươi giây
Lần tới khi bạn định push từng phần tử vào một hàng đợi ưu tiên trong vòng lặp để dựng nó từ một mảng có sẵn, dừng lại và hỏi: thư viện của tôi có heapify/make_heap không? Gần như chắc là có, và nó O(n) một phát thay vì gọi push n lần. Và nếu bạn từng nghĩ "để tôi bỏ hết vào heap rồi đọc ra là có mảng sắp xếp", hãy thử in mười phần tử đầu của mảng heap ra: bạn sẽ thấy phần tử đầu đúng là nhỏ nhất, còn chín phần tử sau thì lộn xộn. Đó là lời nhắc rằng heap là một cấu trúc ưu tiên, không phải một cấu trúc sắp xếp — nó làm đúng một việc, cực nhanh, và bạn nên dùng nó cho đúng việc đó.
