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}

Lấy phần tử đầu tiên ra là d bỏ vào mảng C = {d f k p r y }
Khi này A = { c b a }
Tạo heap cho A = { c a b }


Lấy phần tử đầu tiên ra là c bỏ vào mảng C = {c d f k p r y }
Khi này A = { b a }
Tạo heap cho A = { b a }

Lấy phần tử đầu tiên ra là b bỏ vào mảng C = {b c d f k p r y }
Khi này A = { a }
Tạo heap cho A = { a }

Kết thúc ta có được mảng C đã có thứ tự .

Cải tiến:
Ta có thể hạn chế việc sử dụng thêm mảng C bằng cách tận dụng luôn mảng A ban đầu . Ta làm như sau

A = y r p d f b k a c
Bước 1 :
Lấy y ra
Lấy c ra
Bỏ y vào chổ của c .
Bỏ c vào chỗ của y

Khi ta bỏ y vào chỗ của c thì giống như ta bỏ y vảo mảng C .
Khi này mảng A sẽ coi như gồm 2 phần A = c r p d f b k a ---- y

Bước 2 : tạo heap cho phần đứng trước của A là c r p d f b k a
Phần sau là chứa y để nguyên

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
...........
Làm tương tự đến khi kết thúc

Qua VD ta thấy rằng phần quan trọng nhất là làm sao sinh ra heap từ một mảng cho trước

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
 

void Sortable_List<Record>::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 ;

                           }

               }

               entry[low] = current ; 

 }

 

 Tạo ra heap lúc ban đầu , lúc chưa chạy giải thuật

 void Sortable_List<Record>::bulidheap()

 {

           int low ;

           for ( low = count / 2- 1; low >= 0 ; low -- )

           {

                   Record current = entry[low] ;

                   insert_heap(current, low, count -1) ;

           }

 }

 

 void Sortable_List<Record>::heapsort ()

 {

             Record current ;

             int last_unsorted ;

             buildheap() ;

             for ( last_unsorted = count -1 ; last_unsorted > 0 ; last_unsorted -- )

             {

                       current = entry[ last_unsorted] ;

                       entry[last_unsorted]  = entry[0] ;

                       insert_heap(current,0,last_unsorted-1) ;

             }

 }