Xây heap: make_heap nhanh hơn push từng cái tới 6,3 lần

Nghĩ về một sơ đồ tổ chức mà luật duy nhất là: mỗi sếp phải "nhỏ hơn" (ưu tiên cao hơn) mọi nhân viên dưới mình. Người nhỏ nhất luôn ngồi ghế trên cùng. Muốn có sơ đồ như vậy từ một đám người, bạn có hai cách: tuyển từng người một rồi thăng chức dần cho tới khi họ về đúng chỗ, hoặc xếp tất cả vào ghế bừa rồi sắp lại từ dưới lên trong một lượt. Cả hai ra cùng một sơ đồ hợp lệ, nhưng công sức khác hẳn nhau — và đó chính là chuyện xây một heap.

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 — đúng cái sơ đồ tổ chức mà bạn tra "sếp của ghế số i" bằng một phép tính thay vì lần theo dây. Đâ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ôi trường đo: container gcc:13 trên host ARM AArch64, g++ -O2, N=10 triệu, mỗi số lấy MIN sau warmup. Con số đổi theo máy; cái cần nhìn là bậc O(n) vs O(n log n) khi xây, và pop đắt hơn push do mẫu truy cập.)

Hai niềm tin đối nghịch, cùng sai

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". Con số 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.

Nhưng có một niềm tin thứ hai, phổ biến hơn, cũng sai: "heap là một cây nên phải cần node và con trỏ". Không — 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 một byte cấp phát node nào. Chữ "cây" ở đây là cách nghĩ, không phải cách lưu.

Về đến code hằng ngày

Điều đầ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.

Điều 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ộ.

Chỗ này người viết Java, Python hay làm hệ thống sẽ thấy heap ở khắp nơi dưới cái tên hàng đợi ưu tiên. Java PriorityQueue là một binary heap trên mảng, và constructor nhận sẵn một Collection chạy heapify O(n) thay vì add từng cái — đúng bài học ở trên, nên nạp cả collection một lần thì nhanh hơn add trong vòng lặp. Python heapq thao tác thẳng trên list (mảng), có heapify O(n) và nlargest/nsmallest dùng heap kích thước k cho top-k. Ở tầng hệ thống, hàng đợi ưu tiên là xương sống của bộ lập lịch (scheduler) hệ điều hành và các hàng đợi sự kiện theo thời gian (timer wheel là biến thể tối ưu), còn Dijkstra và A* trong định tuyến mạng/bản đồ đều đứng trên heap. Cùng một cấu trúc mảng-khéo-léo, xuất hiện lại mỗi khi cần "lấy cái ưu tiên nhất tiếp theo".

Muốn tự thấy thì 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. Vài phút đó 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 đỏ.