Sắp xếp heap sort

Heap sort là một ứng dụng của cấu trức dữ liệu heap. ta có thể sử dụng Max Heap hoặc Min Heap để thực hiện heap sort.

Giả sử ta muốn sắp xếp các phần tử trong mảng A[] theo thứ tự tăng dần. Ta có thể dùng max heap để làm điều này bởi dựa vào đặc tính của max heap, node gốc trong max heap là node có giá trị lớn nhất. Như vậy sau khi tìm được node lớn nhất ta có thể lưu nó lại một nơi khác, thay thế nó bằng một giá trị khác, nhỏ hơn ở trong cây và tiếp tục áp dụng hàm run_maxheap() để tìm được giá trí lớn nhất thứ 2. Cụ thể các bước như sau:

  • Bước đầu tiên, ta tạo một max heap của các phần tử trong mảng A[] bởi sử dụng hàm run_maxheap() (hàm này đã được cài đặt trong bài học về Max Heap).

  • Bây giờ ta thu được phần tử có giá trị lớn nhất trong mảng, chính là node gốc của heap hay phần tử A[1] trong mảng. Đổi chỗ phần tử này với phần tử cuối cùng của mảng A (vì phần tử cuối cùng thường là những phần tử có giá trị nhỏ nhất).

  • Sau khi đổi chỗ, ta tiếp tục tạo max heap mới của các phần tử trong mảng trừ phần tử cuối cùng, vì phần tử này đã được sắp xếp đúng vị trí (ta sắp xếp mảng theo thứ tự tăng dần, do vậy phần tử cuối của mảng sẽ là phần tử có giá trị cao nhất) và do vậy ta giảm kích thước của heap đi 1.

  • Lập lại bước 2 và bước 3 cho đến khi tất cả các phần tử trong mảng được sắp xếp đúng theo thứ tự tăng dần.

  • Và ta thu được mảng đã được sắp xếp.

Cài đặt heap sort

Giả sử ta có mảng A với N phần tử.

Gọi hàm thực hiện sắp xếp dựa vào max heap là max_heap_sort(), tuân theo các bước đã để cập ở trên, nội dung của hàm max_heap_sort() như sau:

void max_heap_sort(int A[ ])
{
    int heap_size = N;
    run_maxheap(A);
    for(int i = N; i>=2 ; i-- )
    {
        swap(A[ 1 ], A[ i ]);
        max_heap(A, 1, --heap_size);
    }
}

Độ phức tạp: O(NlogN)

Như ta đã biết, độ phức tạp của hàm max_heap() là O(logN), run_maxheap() là O(N) và chúng ta chạy hàm max_heap() N-1 lần trong hàm max_heap_sort().

do vậy độ phức tạp của hàm max_heap_sort() sẽ bằng O(NlogN).

Ví dụ về heap sort theo max heap

Trong hình bên dưới, Ta có mảng A với 6 phần tử chưa được sắp xếp. Ta thực hiện tạo max heap cho mảng này:

Hình 1: Tạo max heap cho mảng

Sau khi tạo max heap, các phần tử trong mảng sẽ như sau:

 

Hình 2: Mảng sau khi tạo max heap

Và các bước xử lý cần có tiếp theo để thu được mảng sắp xếp là:

Bước 1: 8 được đổi chỗ cho 5.

Bước 2: 8 được bỏ ra khỏi heap vì nó đã được sắp xếp đúng vị trí.

Bước 3: Max heap mới được tạo và 7 được đổi chỗ cho 3.

Bước 4: 7 được bỏ ra khỏi heap vì nó đã được sắp xếp đúng vị trí.

Bước 5: Max heap mới được tạo với 4 phần tử còn lại. 5 được đổi chỗ cho 1.

Bước 6: 5 được bỏ ra khỏi heap vì nó đã được sắp xếp đúng vị trí.

Bước 7: Max heap mới được tạo với 3 phần tử còn lại. 4 được đổi chỗ cho 3.

Bước 8: 4 được bỏ ra khỏi heap vì nó đã được sắp xếp đúng vị trí.

Bước 9: Max heap mới được tạo với 2 phần tử còn lại. 3 được đổi chỗ cho 1.

Bước 10: 3 được bỏ ra khỏi heap vì nó đã được sắp xếp đúng vị trí.

Bước 11: heap còn lại duy nhất một phần từ, ta bỏ nó ra khỏi heap và thu được mảng đã được sắp xếp theo thứ tự tăng dần.

Hình 3: mô tả thuật toán heap sort

Hình trên đã mô tả toàn bộ hoạt động của thuật toán heap sort dùng max heap. Ta có nhiều cách để thực hiện heap sort, ta có thể dùng cách trên hoặc duyệt max heap đã được tạo ra và sắp xếp lại nó theo mỗi level dùng cách duyệt theo chiều rộng. Tuy nhiên cách trên là cách hiệu quả, dễ cài đặt và tối ưu về mặt hiệu năng cửa chương trình.

Toàn bộ mã nguồn thực hiện chương trình heap sort như sau:

#include <iostream> 
using namespace std;

int N = 6; /* Số phần tử của heap */
void max_heap(int A[], int i, int heap_size) {
    int largest; /* Chỉ số của phần tử lớn nhất trong bộ ba: node hiện tại
                         con bên trái, và con bên phải của nó */
    int left = 2 * i; /* Vị trí của con bên trái */
    int right = 2 * i + 1; /* Vị trí của con bên phải */
    if (left <= heap_size and A[left] > A[i]) /* heap_size là số phần tử trong mảng*/
        largest = left;
    else
        largest = i;
    if (right <= heap_size and A[right] > A[largest])
        largest = right;
    if (largest != i) {
        swap(A[i], A[largest]); /* Thực hiện đổi chỗ hai phần tử nếu 
                                              giá trị của node cha nhỏ hơn node con */
        max_heap(A, largest, heap_size); /* Gọi đệ quy node tại vị trí mới */
    }
}

void run_maxheap(int A[]) { /* Áp dụng hàm max_heap cho tất cả các node
                                               trừ node lá */
    for (int i = N / 2; i >= 1; i--) {
        max_heap(A, i, N);
    }
}

void max_heap_sort(int A[ ])
{
    int heap_size = N;
    run_maxheap(A);
    for(int i = N; i>=2 ; i-- )
    {
        swap(A[ 1 ], A[ i ]);
        max_heap(A, 1, --heap_size);
    }
}

int main() {
    int A[N+1] = {-1,8,4,7,1,3,5}; /* Mảng chứa 7 phần tử, với phần tử 
                                      của heap bắt đầu từ vị trí 1 tới N
                                      phần tử dầu tiên của mảng chỉ có tác
                                      dụng làm lấp đầy mảng, giá trị bất kỳ */
    max_heap_sort(A);
    printf("\n\tGiá trị của mảng sau khi áp dụng hàm max_heap_sort\n");
    printf("\t");
    for (int i = 0; i < N+1; i++) { /* In ra giá trị của mảng sau khi sắp xếp với 
                                                 hàm max_heap_sort */
        printf("%d    ", A[i]);
    }
}

Kết quả chương trình sau khi chạy và kiểm tra tại https://www.onlinegdb.com.

Mã nguồn trên gitlab:

https://gitlab.com/thevngeek/basic-data-structure/blob/master/max_heap_sort.cpp

Tham khảo

  1. https://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_vun_%C4%91%E1%BB%91ng

  2. https://www.hackerearth.com/fr/practice/data-structures/trees/heapspriority-queues/tutorial/

 

** Nếu bạn muốn viết các nội dung đặt biệt thì hãy làm theo hướng dẫn sau

Xem thêm 10 bình luận
Viết blog mới của bạn
Báo lỗi trang
Đang tải