Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn Phí
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Diễn đàn hỏi đáp học thuật - Download Tài Liệu Miễn PhíĐăng Nhập

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


descriptionThuật toán Heap Sort EmptyThuật toán Heap Sort

more_horiz
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:
Thuật toán Heap Sort Hep_so10

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();
}

descriptionThuật toán Heap Sort EmptyRe: Thuật toán Heap Sort

more_horiz
thank.cai ma e dang can Very Happy
privacy_tip Permissions in this forum:
Bạn không có quyền trả lời bài viết
power_settings_newLogin to reply