HEAP SORT


Ta xem danh sách n phần tử a_0,a_1,a_(n-1) 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*(i+1) nhỏ hơn n. Thuật toán được mô tả như sau:
    - Xây dựng Heap sao cho với 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ị nút gốc với nút thứ n – 1 và xây dựng lại Heap mới với n – 2 nút và tiếp tục hoán vị nút gốc với nút lá cuối của cây mới sau n – 2 bước ta sẽ thu được danh sách được sắp xếp theo thứ tự.


Code:

#include <iostream.h>
#include <conio.h>
#define max 100
void NhapMang(int A[],int n) {
   for(int i=0; i<n; i++) {
      cout<<"nhap Phan tu thu A["<<i<<"] =";
      cin>>A[i];
   }
}
void XuatMang(int A[],int n) {
   cout<<endl;
   for(int i=0; i<n; i++)
      cout<<A[i]<<"\t";
}
void Swap(int &a,int &b) {
   int temp = a;
   a = b;
   b = temp;
}
//hoan vi nut cha thu i phai lon hon nut con
void Heapify(int A[],int n, int i) {
   int Left = 2*(i+1)-1;
   int Right = 2*(i+1);
   int Largest;
   if(Left<n && A[Left]>A[i])
      Largest = Left;
   else
      Largest = i;
   if(Right<n && A[Right]>A[Largest])
      Largest = Right;
   if(i!=Largest) {
      Swap(A[i],A[Largest]);
      Heapify(A,n,Largest);
   }
}
//xay dung Heap sao cho moi nut cha luon lon hon nut con tren cay
void BuildHeap(int A[], int n) {
   for(int i = n/2-1; i>=0; i--)
      Heapify(A,n,i);
}
void HeapSort(int A[], int n) {
   BuildHeap(A,n);
   for(int i = n-1; i>0; i--){
      Swap(A[0],A[i]);
      Heapify(A,i,0);
   }
}
void main() {
   int A[max], n;
   clrscr();
   cout<<"Nhap so phan tu:";
   cin>>n;
   NhapMang(A,n);
   cout<<"\nMang vua nhap la:";
   XuatMang(A,n);
   cout<<"\nSap xep theo Heap Sort:";
   HeapSort(A,n);
   XuatMang(A,n);
   getch();
}