+ Tư tưởng của thuật toán Heap-Sort [săp xếp chồng đống]
Ta xem danh sách n phần tử a1, a2, a3,. một là cây nhị phân.
Cây nhị phân này được xác định như sau. tại nút thứ i tương ứng với chỉ số thứ i của mảng có con trái là nút 2*[i+1]-1 và con phải 2*[i+1] nếu 2*[i+1]-1 và 2* .
Thuật toán được mô tả như sau.
- Build Heap [đống] sao cho mọi nút cha đều có giá trị lớn hơn nút con. Khi đó nút gốc là nút có giá trị lớn nhất.
- Hoán vị trí nút gốc với nút thứ n – 1 và xây dựng lại Heap mới với nút n – 2 và tiếp tục khôi phục vị trí nút gốc với nút lá cuối của cây mới sau n – 2 bước .
Ví dụ. xem xét danh sách trước khi sắp xếp
+ Cài đặt thuật toán [Code Turbo C++]
#include
#include
#define max 100
// nhap day
void NhapMang[int A[],int n] {< . =Largest] {
for[int i=0; i