Sắp xếp vun đống¶

Tip

Trước khi đọc phần này, vui lòng đảm bảo bạn đã hoàn thành chương "Đống".

Sắp xếp vun đống là một thuật toán sắp xếp hiệu quả dựa trên cấu trúc dữ liệu đống. Chúng ta có thể triển khai sắp xếp vun đống bằng các thao tác dựng đống và loại bỏ phần tử đã được giới thiệu trước đó.

Nhập vào mảng và xây dựng một đống cực tiểu (min-heap), tại thời điểm đó phần tử nhỏ nhất nằm ở đỉnh đống.
Liên tục thực hiện các thao tác loại bỏ phần tử và ghi lại các phần tử đã loại bỏ theo thứ tự để thu được một chuỗi được sắp xếp theo thứ tự tăng dần.

Mặc dù phương pháp trên là khả thi, nhưng nó yêu cầu một mảng bổ sung để lưu các phần tử được lấy ra (popped), điều này khá lãng phí không gian. Trong thực tế, chúng ta thường sử dụng một phương pháp triển khai trang nhã hơn.

Quy trình thuật toán¶

Giả sử độ dài mảng là \(n\). Quy trình của sắp xếp vun đống được minh họa trong hình dưới đây.

Nhập vào mảng và xây dựng một đống cực đại (max-heap). Sau khi hoàn thành, phần tử lớn nhất nằm ở đỉnh đống.
Hoán đổi phần tử đỉnh đống (phần tử đầu tiên) với phần tử đáy đống (phần tử cuối cùng). Sau khi hoán đổi hoàn tất, giảm độ dài đống đi \(1\) và tăng số lượng phần tử đã sắp xếp thêm \(1\).
Bắt đầu từ phần tử đỉnh đống, thực hiện thao tác vun đống từ trên xuống dưới (sift down). Sau khi vun đống hoàn tất, tính chất đống được phục hồi.
Lặp lại bước 2. và 3.. Sau \(n - 1\) vòng, mảng đã được sắp xếp.

Tip

Trên thực tế, thao tác loại bỏ phần tử cũng bao gồm các bước 2. và 3., với bước bổ sung là loại bỏ phần tử.

Trong mã nguồn dưới đây, chúng ta sử dụng cùng một hàm sift_down() cho thao tác vun đống từ trên xuống dưới như trong chương "Đống". Cần lưu ý rằng vì độ dài của đống giảm đi khi phần tử lớn nhất được rút ra, chúng ta cần thêm tham số độ dài \(n\) vào hàm sift_down() để xác định độ dài hiệu dụng hiện tại của đống. Mã nguồn cụ thể như sau:

[file]{heap_sort}-[class]{}-[func]{heap_sort}

Đặc điểm của thuật toán¶

Độ phức tạp thời gian là \(O(n \log n)\), sắp xếp vun đống không thích ứng: Quá trình dựng đống tốn thời gian \(O(n)\). Việc rút phần tử lớn nhất ra khỏi đống tốn thời gian \(O(\log n)\), và thao tác này được lặp lại tổng cộng \(n - 1\) vòng.
Độ phức tạp không gian là \(O(1)\), sắp xếp vun đống tại chỗ: Một vài biến con trỏ sử dụng không gian \(O(1)\) không đổi. Việc hoán đổi phần tử và vun đống đều được thực hiện trực tiếp trên mảng ban đầu.
Sắp xếp không ổn định: Khi hoán đổi phần tử đỉnh đống và phần tử đáy đống, vị trí tương đối của các phần tử bằng nhau có thể bị thay đổi.