+ Trả lời chủ đề
Hiện kết quả từ 1 tới 1 của 1

Chủ đề: Thuật toán Heap Sort

  1. #1
    Status : ngovanhieu_Alpha đang ẩn
    Tham gia ngày : Aug 2011
    Bài gửi : 200

    Thuật toán Heap Sort

    Thuật toán Heap Sort

    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:
    Mã:
    #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();
    }
    Lần sửa cuối bởi ngovanhieu_Alpha; 06-08-2011 lúc 03:07 PM

+ Trả lời chủ đề

Quyền viết bài

  • Bạn không thể gửi chủ đề mới
  • Bạn không thể gửi trả lời
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
Trang Chủ Việc Làm Gia Sư Gia sư