Thao tác xây dựng đống

Trong một số trường hợp, chúng ta muốn xây dựng một đống bằng cách sử dụng tất cả các phần tử của một danh sách, và quá trình này được gọi là "thao tác xây dựng đống".

Triển khai bằng cách chèn phần tử

Đầu tiên, chúng ta tạo một đống trống, sau đó duyệt qua danh sách, thực hiện lần lượt "thao tác chèn phần tử" trên từng phần tử. Điều này có nghĩa là thêm phần tử đó vào cuối đống rồi thực hiện vun đống "từ dưới lên trên" cho phần tử đó.

Mỗi lần một phần tử được chèn vào đống, chiều dài của đống sẽ tăng lên một. Vì các nút được thêm vào cây nhị phân theo tuần tự từ trên xuống dưới, đống được xây dựng "từ trên xuống dưới".

Cho trước \(n\) phần tử, thao tác chèn mỗi phần tử mất thời gian \(O(\log{n})\), do đó độ phức tạp thời gian của phương pháp xây dựng đống này là \(O(n \log n)\).

Triển khai bằng cách duyệt vun đống

Trên thực tế, chúng ta có thể triển khai một phương pháp xây dựng đống hiệu quả hơn gồm hai bước.

1. Thêm nguyên trạng tất cả các phần tử của danh sách vào đống, tại thời điểm này tính chất đống vẫn chưa được thỏa mãn.
2. Duyệt qua đống theo thứ tự ngược lại (ngược với thứ tự duyệt theo mức), thực hiện lần lượt vun đống "từ trên xuống dưới" cho từng nút không phải là nút lá.

Sau khi vun đống cho một nút, cây con có gốc tại nút đó sẽ trở thành một đống con hợp lệ. Vì chúng ta duyệt theo thứ tự ngược lại, đống được xây dựng "từ dưới lên trên".

Lý do chọn duyệt theo thứ tự ngược lại là vì nó đảm bảo các cây con bên dưới nút hiện tại đã là các đống con hợp lệ, do đó việc vun đống cho nút hiện tại mới có hiệu quả.

Một điều đáng lưu ý là do các nút lá không có nút con, chúng hiển nhiên là các đống con hợp lệ và không cần phải vun đống. Như được hiển thị trong đoạn mã dưới đây, nút không phải lá cuối cùng chính là nút cha của nút cuối cùng; chúng ta bắt đầu từ nút đó và tiến hành vun đống trong khi duyệt theo thứ tự ngược lại:

[file]{my_heap}-[class]{max_heap}-[func]{__init__}

Phân tích độ phức tạp

Tiếp theo, hãy thử suy luận độ phức tạp thời gian của phương pháp xây dựng đống thứ hai này.

• Giả sử cây nhị phân hoàn chỉnh có \(n\) nút, thì số lượng nút lá là \((n + 1) / 2\), trong đó \(/\) là phép chia làm tròn xuống. Do đó, số lượng nút cần thực hiện vun đống là \((n - 1) / 2\).
• Trong quá trình vun đống từ trên xuống dưới, mỗi nút có thể chìm xuống tối đa đến một nút lá, do đó số lần lặp tối đa là chiều cao của cây nhị phân, \(\log n\).

Nhân hai giá trị này với nhau, chúng ta thu được độ phức tạp thời gian cho quá trình xây dựng đống là \(O(n \log n)\). Tuy nhiên, ước tính này không chính xác vì nó không tính đến đặc tính rằng cây nhị phân có số lượng nút ở các tầng dưới nhiều hơn rất nhiều so với các tầng trên.

Hãy thực hiện một phép tính chính xác hơn. Để đơn giản hóa việc phân tích, hãy giả định một "cây nhị phân hoàn hảo" có \(n\) nút và chiều cao \(h\); giả định này không ảnh hưởng đến tính đúng đắn của kết quả.

Như được hiển thị ở hình trên, số lần lặp tối đa của thao tác "vun đống từ trên xuống dưới" cho một nút bằng khoảng cách từ nút đó đến một nút lá, và đó chính là chiều cao của nút. Do đó, chúng ta có thể cộng tổng của "số lượng nút \(\times\) chiều cao của nút" ở mỗi tầng để thu được tổng số lần lặp vun đống của tất cả các nút.

\[ T(h) = 2^0h + 2^1(h-1) + 2^2(h-2) + \dots + 2^{(h-1)}\times1 \]

Việc đơn giản hóa biểu thức trên đòi hỏi một số kiến thức đại số về dãy số ở bậc trung học phổ thông. Đầu tiên, nhân \(T(h)\) với \(2\) ta được:

\[ \begin{aligned} T(h) & = 2^0h + 2^1(h-1) + 2^2(h-2) + \dots + 2^{h-1}\times1 \newline 2 T(h) & = 2^1h + 2^2(h-1) + 2^3(h-2) + \dots + 2^{h}\times1 \newline \end{aligned} \]

Sử dụng phương pháp nhân dịch chuyển rồi trừ vế theo vế, lấy phương trình thứ hai \(2 T(h)\) trừ đi phương trình thứ nhất \(T(h)\), ta thu được:

\[ 2T(h) - T(h) = T(h) = -2^0h + 2^1 + 2^2 + \dots + 2^{h-1} + 2^h \]

Quan sát biểu thức trên, ta thấy phần tổng của các lũy thừa của \(2\) là một cấp số nhân, có thể tính trực tiếp bằng công thức tính tổng, thu được:

\[ \begin{aligned} T(h) & = 2 \frac{1 - 2^h}{1 - 2} - h \newline & = 2^{h+1} - h - 2 \newline & = O(2^h) \end{aligned} \]

Hơn nữa, một cây nhị phân hoàn hảo có chiều cao \(h\) có \(n = 2^{h+1} - 1\) nút, do đó độ phức tạp là \(O(2^h) = O(n)\). Suy luận này cho thấy độ phức tạp thời gian của việc xây dựng một đống từ một danh sách đầu vào là \(O(n)\), vô cùng hiệu quả.