Nó hoạt động như thế nào?

Đống nhị phân nằm trong một mảng thông thường. Với nút ở chỉ số i (bắt đầu từ 0), các nút con nằm ở 2*i + 1 và 2*i + 2. Cách đánh chỉ số đó chính là mẹo giúp lưu cây trong một mảng.

Quy trình từng bước:

1. Tạo đống cực đại: sắp xếp lại mảng để mỗi nút cha có giá trị >= các nút con. Giá trị lớn nhất sẽ nằm ở chỉ số 0.
2. Lấy giá trị lớn nhất: đổi chỗ nút gốc (lớn nhất) với phần tử cuối cùng của đống, rồi thu nhỏ đống đi một phần tử để giá trị lớn nhất nằm ở cuối, tại vị trí cuối cùng trong mảng đã sắp xếp.
3. Khôi phục bằng cách sàng xuống: nút gốc mới có thể không đúng vị trí, vì vậy hãy sàng nó xuống (đổi chỗ nó với nút con lớn hơn, rồi lặp lại) cho đến khi đống thỏa mãn tính chất của nó.
4. Lặp lại cho đến khi đống trống. Lúc này, mảng đã được sắp xếp theo thứ tự tăng dần.

Ví dụ với [4, 10, 3, 5, 1]:

• Tạo đống cực đại: [10, 5, 3, 4, 1].
• Đổi chỗ nút gốc 10 với phần tử cuối rồi sàng xuống, sau đó lặp lại với 5, 4, 3.
• Kết quả: [1, 3, 4, 5, 10].