Heap Sort

Định nghĩa Heap:

Heap là một cây nhị phân hoàn chỉnh trong đó giá trị khóa ở nút gốc luôn lớn hơn giá trị khóa ở 2 con ,cây con trái và cây con phải cũng là một Heap.

Tư tưởng :

- Cây nhị phân biểu diễn bảng khoá được biến đổi để trở thành một đống(heap).

- Giai đoạn sắp xếp:

1. Giai đoạn tạo đống : tạo Heap có n giá trị khóa ,Heap có n/2 nút cha chúng ta vun heap từ dưới lên (botton up) với các gốc n/2 đến 1 lặp các phép xử lý vun heap với 2 con đã là heap .

Trong khi khóa của nút cha nhỏ hơn khóa của nút hai con ,tuyển khóa lớn hơn thay cho nút cha và tiếp tục đi xuống để tìm vị trí thích hợp đặt khóa nút cha .

2. Giai đoạn sắp xếp : lặp 1 quá trình lấy các phần tử ra khỏi heap ,luôn lấy từ gốc .

- Chặt gốc ,mỗi lần lấy heap còn (n-1) phần tử ,phần tử cuối cùng không được lưu trữ ,sẽ đưa vào vị trí gốc ,sau đó giá trị khóa của gốc vừa chặt sẽ đựơc đẩy vào vị trí cuối cùng

è Vi phạm tính chất của heap phải vun lại heap từ gốc và quá trình kết thúc khi chặt n-1 phần tử và dãy đã được xếp .

Thủ tục vun đống:

void Adjust(int X[50],int i,int n)

{

int key=X[i];

int j=i+i;

while(j<=n)

{

if(j<n&&X[j]<X[j+1])j=j+1;

if(key>X[j])

{

X[j/2]=key;

return;

}

X[j/2]=X[j];

j=j+j;

}

X[j/2]=key;

}

Thủ tục Heap sort

void HeapSort(int X[50],int n)

{

int i,tmp;

for(i=n/2;i>=1;i--)

Adjust(X,i,n);

for(i=n;i>=1;i--)

{

tmp=X[1];

X[1]=X[i];

X[i]=tmp;

Adjust(X,1,i-1);

}

}

+ Độ phức tạp của thuật toán :

Đánh giá giải thuật :

+ Độ phức tạp : cỡ O(nlog2n)

+ Ưu điểm :nhanh ,hiệu quả và không đòi hỏi về

không gian bộ nhớ .

+ Nhược điểm :- khi dãy số sắp xếp đã có thứ tự

thì giải thuật này tỏ ra không hiệu quả .

- Khó cài đặt .