Đồ Án Viết chương trình mô phỏng thuật toán sắp xếp vun đống

I. Giới thiệu thuật toán sắp xếp vun đống (Heap sort)
Sắp xếp vun đống (heapsort) được đề xuất vào năm 1964 bởi J.W.J. Williams trên tạp chí Communication of the ACM
Là một trong các phương pháp sắp xếp chậm nhất trong các thuật toán có độ phức tạp O(nlog2n). Nhưng lại đạt ưu điểm ở tính đơn giản của việc cài đặt không đòi hỏi đệ quy phức tạp như Quick sort và sữ dụng mảng phụ như Merge sort.

II. Ý tưởng của thuật toán Heap sort
* Giả sử tập cần xếp theo thứ tự tăng dần:
- Heap sort xây dựng 1 heap out của tập dữ liệu à loại bỏ phần tử lớn nhất và đặt nó vào cuối dãy sắp xếp.
- Tiếp tục heap out dãy còn lại và mang phần tử lớn nhất của dãy đó về kế cuối (sau phần tử lớn nhất được mang bước trước).
- Thao tác này được lặp lại cho đến khi không còn phần tử bên trái dãy heap và mảng sắp xếp đã đầy.
* Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heap sort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).

* Ta có thể biểu diễn ý tưởng của thuật toán heap sort trên cây nhị phân:
Heap là một cây nhị phân đầy đủ và giá trị mỗi nút không bao giờ bé hơn giá trị nút con nó.