thuật toán heap sort - sắp xếp vun đống, (cây)

thuật toán heap sort - sắp xếp vun đống, (cây)

Heap Sort tận dụng được các phép so sánh ở bước i-1 mà thuật toán sắp xếp chọn trực tiếp không tận dụng được
Để làm được điều này Heap sort thao tác dựa trên cây.
Ở cây trên, phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i +1, do đó phần tử ở nút gốc là phần tử lớn nhất.
Nếu loại bỏ gốc ra khỏi cây, thì việc cập  nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác thì bảo toàn.
Bước kế tiếp có thể sử dụng lại kết quả so sánh của bước hiện tại.
Vì thế độ phức tạp của thuật toán O(nlog2n)

Giai đoạn 1 : Hiệu chỉnh dãy số ban đầu thành heap
Giai đoạn 2:  Sắp xếp dãy số dựa trên heap:
Bước 1:Đưa phần tử  lớn  nhất về vị trí đúng ở cuối dãy:             r = n-1;  Swap (a1 , ar );
Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r = r-1;        Hiệu chỉnh phần còn lại của dãy từ  a1 , a2 ... ar thành một heap.
Bước 3:
       Nếu r>1 (heap còn phần tử ): Lặp lại Bước 2   Ngược lại : Dừng
Heap: Là một dãy các phần tử  al, al+1 ,... , ar  thoả các quan hệ với mọi i  [l, r]:
ai  a2i+1
ai  a2i+2 // (ai , a2i+1), (ai , a2i+2 ) là các cặp phần tử liên đới
Cho dãy số  : 12   2   8   5  1   6   4  15
Giai đoạn 1: Hiệu chỉnh dãy ban đầu thành Heap
Giai đoạn 2: Sắp xếp dãy số dựa trên Heap

void shift(int a[],int l,int r)
{
int x,i,j;
i=l;
j=2*i+1;
x=a[i];
while(j<=r)
{ if(j<r)
if(a[j]<a[j+1]) //tim phan tu lon nhat a[j] va a[j+1]

j++; //luu chi so cua phan tu nho nhat trong hai phan tu 
if(a[j]<=x) return;
else
{ a[i]=a[j];
a[j]=x;
i=j;
j=2*i+1;
x=a[i];
}
}
}
void CreateHeap(int a[],int n)
{ int l;
l=n/2-1;
while(l>=0)
{
shift(a,l,n-1);
l=l-1;
}
}
void HeapSort(int a[],int n)
{ int r;
CreateHeap(a,n);
r=n-1;
while(r>0)
{
Swap(a[0],a[r]);//a[0] la nút gốc
r--;
if(r>0)
shift(a,0,r);
}
}