Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Thuật toán Heap Sort

Share
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Thuật toán Heap Sort

Bài gửi  admin on Sat Apr 17, 2010 9:01 am

Ta xem danh sách n phần 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*(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ự.
Ví dụ: xét danh sách trước khi sắp xếp
11 3 5 4 9 15 19 7
Danh sách trên được thể hiện bằng cây theo thuật toán Heap Sort như sau:


Chương trình minh họa:
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();
}

sau_thien_thu
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 4
Join date : 28/04/2011

Re: Thuật toán Heap Sort

Bài gửi  sau_thien_thu on Thu Apr 28, 2011 9:13 pm

thank.cai ma e dang can Very Happy

    Hôm nay: Tue Jun 19, 2018 9:21 pm