Heap là một cấu trúc dữ liệu , có thể được biểu diễn thông qua 2 cách :
-Dạng thứ 1: Dạng cây nhị phân có đặc điểm là node cha thì lớn hơn 2 node con trực tiếp của nó .
-Dạng thứ 2: nếu ta đánh số các node theo thứ tự từ trên xuống và từ trái qua . Bắt đầu là node root
= 0 , thì ta có thể định nghĩa heap thông qua mảng một chiều , có đặc điểm là phần tử thứ k sẽ lớn
hơn các phần tử thứ 2k+1 và 2k+2 . Ta có thể dễ nhận thấy là phàn tử thứ 0 sẽ tương ứng với root
trong cây ở cách biểu diễn thứ 1
Nguyên tắc sắp xếp của heap sort
Dựa vào tính chất của heap trong cách biểu diễn thứ 1 và thứ 2 , ta có thể thấy phần tử đầu tiên
trong cách biểu diễn theo mảng sẽ là phần tử lớn nhất ---> cách sắp xếp đơn giản là : ( Gọi mảng
ban đầu là A )
Khởi tạo : Tạo heap từ mảng ban đầu đã cho (mảng A )
1. Lấy phần tử đầu tiên trong mảng ra bỏ vào mảng kết quả
2. Tạo lại heap từ mảng A
3.Quay lại bước 1
VD : Ta lấy một mảng đã được tạo thành một heap :
y r p d f b k a c
Lấy phần tử đầu tiên là y bỏ vào mảng kết quả C = { y }
khi này A = r p d f b k a c
Tạo heap A = r f p d c b k a
Lấy phần tử đầu tiên ra là r bỏ vào mảng C = { r y }
Khi này A = { f p d c b k a }
Tạo heap cho A = { p f k d c b a}
Lấy phần tử đầu tiên ra là p bỏ vào mảng C = { p r y }
Khi này A = { f k d c b a }
Tạo heap cho A = { k f b d c a}
Lấy phần tử đầu tiên ra là k bỏ vào mảng C = { k p r y }
Khi này A = { f b d c a }
Tạo heap cho A = { f d b a c}
Lấy phần tử đầu tiên ra là f bỏ vào mảng C = { f k p r y }
Khi này A = { b d c a }
Tạo heap cho A = { d c b a}

Sau đây là phần code cho phần cải tiến
Giải thuật
Post Condition : Dùng để phục hồi lại heap .
Pre Condition :
Ta sẽ có A mới là : r f p d c b k a -- y
Quay lại bước 1 : Lấy r , a ra và swap r và a
A sẽ thành A= a f p d c b k -- r y
Tạo heap cho A = p f k d c b a -- r y
Thì khi này current chính là a
low là 0
high là 7
CODEvoid Sortable_List::insert_heap(const Record ¤t, int low , int high )
{
int large;
large = 2*low+1;
while ( large <= high ) {
if (large < high && entry[large] < entry[large+1] )
large ++;
if(current >= entry[large] )
{
break;
}
else
{
entry[low] = entry[large];
low = large;
large = 2 * low + 1;

{
int end=n;
MakeHeap(a,n);
while (end > 0)
{ hoanvi(&a[end],&a[1]);
ADHeap(a, 1, end-1);
end--;
}
}
void MakeHeap(int a[],int n)
{
int i=n/2;
for(i;i>0;i--)
ADHeap(a, i, n);
}
void ADHeap(int a[],int i,int n)
{
int j;
while(i*2<=n)
{
j=i*2;
if((j<n)&&(a[j]<a[j+1]))
j++;
if (a[i]<a[j])
{ hoanvi(&a[i],&a[j]);
i=j;
}
else break;
}
}

{ shift(a,l,n);
l=l-1;
}
}
void hoanvi(int &a,int &b)
{ int temp;
temp=a;
a=b;
b=temp;
}
void nhapmang(int a[],int &n)
{ int i;
printf("/n nhap vao n:");
scanf("%d",&n);
for (i=0;i<n;i++)
{ printf("/n nhap vao %3a[%d]",i);
scanf("%d",&a[i]);
}
}
void xuatmang(int a[], int n)
{
int i;
printf("/n xuat mang");
for(i=0;i<n;i++)
printf("%3d",a[i]);
}
void main()
{ int r,n,a[15];
nhapmang(a,n);printf("%d",a[9]);
xuatmang(a,n);