Thuật toán sắp xếp: HEAP SORT

Ý tưởng

 Xét dãy gồm N phần tử

Hiệu chỉnh dãy thành heap. Đảo vị trí của phần tử đầu dãy với phần tử cuối dãy để đưa phần tử lớn nhất về cuối dãy.

Ta không quan tâm đến phần tử cuối dãy nữa, xem như dãy hiện hành chỉ gồm N-1 phần tử, tính từ 1.

Lặp lại xử lí trên cho đến khi dãy hiện hành chỉ còn một phần tử.

Giải thuật

            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; Hoán vị (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 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. 

Dựa trên tính chất 3 của Heap, ta có thể thực hiện giai đoạn 1 bằng cách bắt đầu từ heap mặc nhiên an/2+1, an/2+1, …., an, lần lượt thêm vào các phần tử an/2, an/2-1, …., a1 ta sẽ nhận được heap theo mong muốn.

Chủ đề liên quan
Thuật toán sắp xếp: HEAP SORT

Cùng chuyên mục

Xem nhiều hôm nay