Thuật toán sắp xếp vun đống (Heap Sort)

<Đang cập nhật...>

Thuật toán Heap sort hay còn gọi là thuật toán vun đống, đây là một thuật toán kinh điển với độ phức tạp cao hơn Bubble sort nhưng hiệu quả cao hơn.
Thuật toán Heap sort sử dụng cây nhị phân để giải thuật. Cây nhị phân này hoạt động theo nguyên tắc, phần tử trên cùng luôn là lớn nhất.





Đặc điểm của heap được sắp xếp:
a. Khi cắt bỏ các phần tử ở ngoài cùng thì nó vẫn là heap.
b. Phần tử ở đầu a1 luôn là phần tử lớn nhất của heap



Giả sử ta có một mảng a[1...x phần tử],
a. Cây cực đại khi a[i]>=a[2*i] và a[i]>=a[2*i+1] với mọi i =1..int(n/2).
b. Cây cực tiểu khi a[i]<=a[2*i] và a[i]<=a[2*i+1]

Để sắp xếp chúng ta có thuật toán sau:
Giả sử chúng ta có một heap với n phần tử
B1. Đưa phần tử lớn nhất ra cuối dãy, đem phần tử lớn nhất ra một biến tạm
B2. Biến phần còn lại trở thành 1 heap với số phần tử mới r=n-1
B3. Nếu r>1 thì vẫn là heap còn phần tử, lặp lại bước 1. Ngược lại thì dừng, xuất ra biến tạm đã sắp xếp

Nguồn: Các thuật toán sắp xếp