Sắp xếp vun đống
Sắp xếp vun đống là sắp xếp chọn với cách tìm giá trị lớn nhất tốt hơn. Nó giữ các giá trị chưa sắp xếp trong một đống, tức một cây lưu ngay bên trong danh sách, nơi giá trị lớn nhất luôn ở đỉnh. Lấy nó ra và sửa lại đống chỉ mất khoảng log n bước thay vì quét toàn bộ.
Cây bên trong danh sách
Đống nhị phân là một cây không cần con trỏ. Vị trí 0 là gốc, và các con của vị trí i là vị trí 2i + 1 và 2i + 2, nên vị trí 1 và 2 là con của gốc, vị trí 3 đến 6 là tầng tiếp theo, và cứ thế. Mọi tầng đều đầy, trừ tầng cuối, được lấp từ trái sang. Trong đống cực đại, mỗi nút cha đều không nhỏ hơn các nút con, nên giá trị lớn nhất luôn ở gốc.
Đẩy xuống
Một thao tác làm mọi việc. Để đẩy một giá trị xuống, so sánh nó với các nút con. Nếu nút con lớn nhất vượt quá giá trị đó, hai giá trị hoán đổi, và giá trị đó được so sánh với các nút con mới. Nó dừng khi không còn nút con nào lớn hơn, hoặc khi chạm đáy. Vì cây chỉ có khoảng log₂ n tầng, một lần đẩy xuống cần tối đa khoảng 2 log₂ n phép so sánh.
Dựng đống, rồi sắp xếp
Để dựng đống, đẩy xuống từng nút cha, từ nút cuối ngược về gốc. Mỗi cây con đã là một đống trước khi nút cha của nó được đẩy xuống vào đó. Sau đó sắp xếp: hoán đổi gốc, tức giá trị lớn nhất, với giá trị cuối của đống. Giá trị đó giờ đã ở vị trí cuối cùng. Đống ngắn đi một, và giá trị vừa đến gốc được đẩy xuống để sửa lại đống. Lặp lại cho đến khi chỉ còn một giá trị.
Ví dụ
Lấy 5, 1, 4, 2, 8. Khi dựng đống, 1 được đẩy xuống dưới 8, rồi 5 được đẩy xuống dưới 8, cho ra 8, 5, 4, 2, 1. Giờ 8 được hoán đổi về cuối; 1 đến gốc và được đẩy xuống qua 5 và 2: 5, 2, 4, 1 | 8. Rồi 5 về cuối và 1 được đẩy xuống qua 4: 4, 2, 1 | 5, 8. Thêm hai vòng nữa là xong: 1, 2, 4, 5, 8, sau 12 phép so sánh và 10 lần hoán đổi.
Ưu và nhược điểm
Sắp xếp vun đống mất thời gian tỉ lệ với n log n kể cả trong trường hợp xấu nhất, và không cần thêm bộ nhớ. Sắp xếp nhanh có thể chậm đến n², còn sắp xếp trộn cần bộ đệm dài bằng danh sách, nên sắp xếp vun đống là phương án dự phòng an toàn: introsort, được thư viện chuẩn C++ dùng, chuyển sang nó khi các bước phân hoạch của sắp xếp nhanh đi chệch. Trên máy tính thật, nó thường chậm hơn cả hai, vì nó nhảy giữa các vị trí cách xa nhau trong danh sách, và nó không ổn định. J. W. J. Williams công bố sắp xếp vun đống, cùng với đống nhị phân, vào năm 1964.
Tự khám phá
Mở ứng dụng và nhấn Bước. Cây phía trên các cột hiển thị đống: giá trị đang được đẩy xuống có màu riêng, nút con được so sánh với nó được tô sáng, và mỗi lần hoán đổi đều hiện ở cả cây lẫn các cột. Khi đống đã dựng xong, hãy xem gốc được hoán đổi về cuối, chuyển sang màu xanh lá và rời khỏi cây.
Câu hỏi thường gặp
Độ phức tạp thời gian của sắp xếp vun đống là bao nhiêu?
O(n log n) trong trường hợp tốt nhất, trung bình và xấu nhất. Dựng đống mất O(n), và mỗi lần trong n − 1 lần lấy ra mất O(log n). Nó sắp xếp tại chỗ với O(1) bộ nhớ thêm.
Sắp xếp vun đống khác sắp xếp chọn thế nào?
Cả hai đều lần lượt lấy giá trị lớn nhất (hoặc nhỏ nhất) còn lại. Sắp xếp chọn tìm nó bằng cách quét toàn bộ phần chưa sắp xếp, mỗi lần n phép so sánh. Sắp xếp vun đống giữ phần chưa sắp xếp trong một đống, nơi giá trị lớn nhất đã ở đỉnh sẵn, và sửa lại đống chỉ tốn khoảng log n phép so sánh.
Ngoài sắp xếp, đống còn dùng để làm gì?
Hàng đợi ưu tiên: đống cho ngay phần tử lớn nhất (hoặc nhỏ nhất) và cho phép thêm hoặc xóa phần tử trong khoảng log n bước. Bộ lập lịch, thuật toán đường đi ngắn nhất của Dijkstra và mô phỏng sự kiện đều dùng nó.
Sắp xếp vun đống có ổn định không?
Không. Việc hoán đổi gốc về cuối di chuyển các giá trị đi rất xa, nên các giá trị bằng nhau có thể đổi thứ tự cho nhau.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử sắp xếp vun đống