Thuật Toán Sắp Xếp: HEAP SORT | Thư Viện Hướng Dẫn

Có thể bạn quan tâm

Ý 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.