Heap nhị phân — cấu trúc đằng sau hàng đợi ưu tiên (priority_queue, heapq) — cho bạn lấy phần tử nhỏ nhất (hoặc lớn nhất) trong O(log n), và là trái tim của Dijkstra, Huffman, top-k, lập lịch. Nhưng nó có hai điều mà nhiều người hiểu sai: cách xây nó rẻ hơn bạn tưởng, và nó không cần một cây con trỏ như BST — nó chỉ là một mảng. Tôi tự cài heap trong container gcc:13, đo push/pop và hai cách xây, và con số cho thấy "xây heap bằng n lần push" đắt hơn make_heap một cách có thể đo được.
Heap là một mảng, không phải cây con trỏ
Điều đầu tiên gây ngạc nhiên: heap nhị phân không dùng node và con trỏ như BST hay std::map. Nó lưu toàn bộ trong một mảng liền mạch, và quan hệ cha-con là số học: con của node ở chỉ số i nằm ở 2i+1 và 2i+2, cha ở (i-1)/2. Không cấp phát node, không con trỏ, không cache miss theo con trỏ ở mỗi bước. Đây là lý do heap thường nhanh và gọn hơn cây con trỏ cho cùng công việc.
Hai thao tác cơ bản, cả hai O(log n):
- PUSH: thêm phần tử vào cuối mảng, rồi "sift-up" — đổi chỗ với cha tới khi đúng thứ tự heap. Đi tối đa log n tầng.
- POP (lấy min): trả về gốc, đưa phần tử cuối lên gốc, rồi "sift-down" — đổi chỗ với con nhỏ hơn tới khi đúng chỗ. Cũng tối đa log n tầng.
Còn xây một heap từ n phần tử có sẵn thì có hai cách cho ra cùng một heap nhưng chi phí khác nhau — và đó là chỗ đo hớ.
Đo: heapify O(n) đánh bại n-push O(n log n)
Với N = 10 triệu, tôi đo trước hai cách xây:
XÂY heap từ 10 triệu phần tử — hai cách CÙNG ra một heap:
Dữ liệu NGẪU NHIÊN:
n lần PUSH lần lượt : 0,0649 s (O(n log n))
HEAPIFY bottom-up : 0,0422 s (O(n)) -> heapify nhanh hơn 1,5x
std::make_heap : 0,0380 s (O(n))
Dữ liệu GIẢM DẦN (worst case cho n-push):
n lần PUSH lần lượt : 0,1162 s (O(n log n))
HEAPIFY bottom-up : 0,0184 s (O(n)) -> heapify nhanh hơn 6,3x
Cả hai cách đều tạo ra một heap hợp lệ, nhưng chi phí khác nhau về bậc. n lần push là O(n log n): mỗi push tốn tới O(log n), làm n lần. Heapify bottom-up (đúng cái std::make_heap làm) là O(n): nó sift-down từ các node ở tầng trong cùng trở lên gốc, và phân tích amortize cho thấy đa số node nằm ở tầng thấp nên sift-down của chúng rất ngắn — tổng lại chỉ O(n), không phải O(n log n).
Với dữ liệu ngẫu nhiên, khoảng cách chỉ 1,5× — vì push một phần tử ngẫu nhiên hiếm khi phải nổi lên xa (nó thường không nhỏ hơn cả chuỗi tổ tiên), nên n-push thực tế gần O(n). Nhưng với dữ liệu giảm dần — worst case, nơi mỗi phần tử mới đều là min nên nổi thẳng lên gốc qua log n tầng — n-push phơi bày đúng bản chất O(n log n) của nó, và heapify nhanh hơn 6,3 lần (0,1162 s so với 0,0184 s). Cùng kết quả, nhưng chọn cách xây sai làm bạn chậm gấp mấy lần khi dữ liệu không may.
Giờ đo push/pop đơn lẻ:
Trên heap 10 triệu phần tử (log₂ 10tr = 24 tầng tối đa):
PUSH (sift-up) : 6,5 ns/push (O(log n))
POP (sift-down) : 298,8 ns/pop (O(log n))
Cả hai đều O(log n), nhưng POP chậm hơn PUSH ~46 lần — một bất đối xứng đáng chú ý. Vì sao? PUSH thêm vào cuối mảng rồi sift-up tới cha — với dữ liệu ngẫu nhiên nó thường dừng sau 1–2 tầng, và cha (i-1)/2 của một phần tử gần cuối nằm gần trong mảng. POP thì luôn sift-down từ gốc qua ~24 tầng, và con ở 2i+1 của một chỉ số lớn nằm rất xa trong mảng — mỗi tầng sift-down là một cache miss tới một vùng cách xa. Đây lại là bài học phần cứng: cùng O(log n) trên giấy, nhưng mẫu truy cập bộ nhớ làm pop đắt hơn push hàng chục lần.
Một lần tôi đo hớ: "n push cũng như make_heap"
Tôi vào đo với niềm tin tự nhiên: "muốn có heap từ một mảng, cứ push từng phần tử vào — kết quả như make_heap thôi". Đo phá tan: n-push là O(n log n), heapify là O(n), và với dữ liệu xấu nhất heapify nhanh hơn 6,3 lần. Chúng ra cùng một heap, nhưng con đường tới đó có chi phí khác bậc. Nếu bạn đã có sẵn cả mảng, dùng make_heap/heapify — đừng push từng cái. Còn niềm tin thứ hai, phổ biến hơn: "heap là một cây nên cần node và con trỏ". Sai — heap nhị phân sống trong một mảng liền mạch với quan hệ cha-con tính bằng chỉ số (2i+1, 2i+2), nên nó thân thiện cache hơn cây con trỏ và không tốn cấp phát node.
Bài học đo lường: push/pop của heap là O(log n), nhưng XÂY heap có hai chi phí khác bậc — n lần push là O(n log n) còn heapify bottom-up (make_heap) là O(n), đo được heapify nhanh hơn 1,5x (ngẫu nhiên) tới 6,3x (dữ liệu xấu nhất); và heap là MẢNG liền mạch (con i -> 2i+1) chứ không cây con trỏ, nên thân thiện cache. Nếu tôi tin "n push cũng vậy" và xây heap bằng vòng lặp push cho dữ liệu lớn từ nguồn bất lợi, tôi tự làm chậm giai đoạn khởi tạo gấp mấy lần mà không hiểu vì sao — trong khi một lời gọi make_heap giải quyết trong O(n).
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: có sẵn cả tập dữ liệu thì heapify một lần, đừng push từng phần tử. std::make_heap, heapq.heapify biến một mảng thành heap trong O(n); dựng bằng vòng lặp push là O(n log n) không cần thiết. Chỉ dùng push khi phần tử đến dần (streaming) và bạn phải duy trì heap sau mỗi lần thêm. Đây là cùng tinh thần "reserve thay vì mọc dần" của phần 2: nếu biết trước dữ liệu, dựng một lần rẻ hơn thêm dần.
Hệ quả thứ hai: nhớ heap là mảng — tận dụng điều đó. Vì heap liền mạch, nó là lựa chọn tốt cho hàng đợi ưu tiên hiệu năng cao (cache tốt, không phân mảnh). Và heapsort chính là "make_heap rồi pop hết" — O(n log n) tại chỗ, không cần bộ nhớ phụ. Khi cần top-k phần tử trong một luồng lớn, một heap kích thước k (giữ k phần tử tốt nhất) cho O(n log k) mà chỉ tốn O(k) bộ nhớ — rẻ hơn nhiều so với sort toàn bộ.
Hệ quả thứ ba là tinh thần đo lường: hai cách cho cùng kết quả có thể khác nhau cả bậc chi phí — đo cách bạn thật sự dùng. Con số mang theo: heap push/pop O(log n) (đo push 6,5 ns, pop 298,8 ns — pop chậm hơn vì sift-down nhảy tới con 2i+1 ở xa = cache miss mỗi tầng); XÂY heap: n-push O(n log n) vs heapify bottom-up/make_heap O(n) — heapify nhanh 1,5x (ngẫu nhiên) tới 6,3x (dữ liệu giảm dần, worst case); heap lưu trong MẢNG (con i -> 2i+1, 2i+2) nên cache tốt hơn cây con trỏ. Có sẵn mảng thì make_heap, đừng push lẻ. Cùng một heap, hai con đường, hai chi phí khác bậc.
Thử ba mươi giây
Lấy một triệu số và xây heap hai cách: một vòng lặp push từng số, và một lời gọi make_heap/heapify trên cả mảng. Bấm giờ cả hai — make_heap nhanh hơn, và nếu bạn nạp dữ liệu đã sắp xếp giảm dần (xấu nhất cho push vào min-heap) thì khoảng cách giãn ra rõ. Rồi in ra vài phần tử đầu của mảng heap và kiểm quan hệ a[i] <= a[2i+1] — bạn sẽ thấy nó là một mảng thuần, không con trỏ nào cả. Cuối cùng, bấm giờ một push so với một pop: pop chậm hơn nhiều, vì sift-down nhảy tới các con ở chỉ số xa gấp đôi trong mảng, dính cache miss. Ba mươi giây đó cho bạn thấy hai điều "hàng đợi ưu tiên O(log n)" giấu đi: xây nó có cách rẻ hơn (O(n) thay vì O(n log n)), và nó chỉ là một mảng khéo léo — không phải một cây con trỏ đắt đỏ.
