Thuật toán sắp xếp vun đống (Heap Sort)

Trong bài viết này, ta sẽ cùng tìm hiểu về cách hoạt động của thuật toán sắp xếp vun đống. Ngoài ra, ta sẽ triển khai ví dụ về cách làm việc của sắp xếp vun đống viết bằng ngôn ngữ lập trình C.

Thuật toán sắp xếp vun đống

Sắp xếp vun đống hay Heap Sort là một thuật toán sắp xếp phổ biến và hiệu quả trong lập trình. Học cách viết thuật toán sắp xếp vun đống đòi hỏi kiến thức về hai loại cấu trúc dữ liệu là mảng và cây.

Tập hợp số ban đầu mà chúng ta muốn sắp xếp được lưu trữ trong một mảng, ví dụ, [12, 5, 78, 36, 25, 34] và sau khi sắp xếp, chúng ta nhận được một mảng đã sắp xếp là [5, 12, 25, 34, 36, 78]

Sắp xếp vun đống hoạt động bằng cách coi các phần tử của mảng như một loại cây nhị phân hoàn chỉnh đặc biệt được gọi là Heap. Điều kiện tiên quyết là bạn phải biết về cấu trúc dữ liệu Heap và cây nhị phân hoàn chỉnh.

Mối quan hệ giữa chỉ số của mảng và phần tử của cây

Một cây nhị phân hoàn chỉnh có một đặc tính mà chúng ta có thể sử dụng để tìm nút con và nút cha của bất kỳ nút nào.

Nếu chỉ số của bất kỳ phần tử nào trong mảng là i, phần tử trong chỉ số 2i+1 sẽ trở thành nút con bên trái và phần tử trong chỉ số 2i+2 sẽ trở thành nút con bên phải. Ngoài ra, nút cha của bất kỳ phần tử nào tại chỉ số i được cho bởi giới hạn dưới là (i-1)/2.

Nút con bên trái của 3 (Chỉ số là 0)
= Phần tử tại chỉ số (2*0+1)
= Phần tử trong chỉ số 1 = 12

Nút con bên phải của 3
= Phần tử tại chỉ số (2*0+2)
= Phần tử trong chỉ số 2 = 9

Tương tự,
Nút con bên trái của 14 (Chỉ số 1)
= Phần tử tại chỉ số (2*1+1)
= Phần tử tại chỉ số 3 = 5

Nút con bên phải của 14
= Phần tử tại chỉ số (2*1+2)
= Phần tử tại chỉ số 4 = 6

Nút con bên trái của 3 (Chỉ số là 0)

= Phần tử tại chỉ số (2*0+1)

= Phần tử trong chỉ số 1 = 12

Nút con bên phải của 3

= Phần tử tại chỉ số (2*0+2)

= Phần tử trong chỉ số 2 = 9

Tương tự,

Nút con bên trái của 14 (Chỉ số 1)

= Phần tử tại chỉ số (2*1+1)

= Phần tử tại chỉ số 3 = 5

Nút con bên phải của 14

= Phần tử tại chỉ số (2*1+2)

= Phần tử tại chỉ số 4 = 6

Ta sẽ xác nhận rằng các quy tắc sẽ luôn đúng cho việc tìm kiếm nút cha của bất kỳ nút nào

Nút cha của 11 (Vị trí 2)
= (2-1)/2  = 1/2 = 0.5 ~ chỉ số 0
= 3

Nút cha của 14 (Vị trí 1)
= (1-1)/2  = chỉ số 0
= 3

Nút cha của 11 (Vị trí 2)

= (2-1)/2 = 1/2 = 0.5 ~ chỉ số 0

= 3

Nút cha của 14 (Vị trí 1)

= (1-1)/2 = chỉ số 0

= 3

Hiểu được việc ánh xạ của các chỉ số của mảng với các vị trí trong cây là rất quan trọng để hiểu được cách thức hoạt động của cấu trúc dữ liệu Heap và cách nó được sử dụng để thực hiện sắp xếp vun đống.

Cấu trúc dữ liệu Heap là gì?

Heap là một cấu trúc dữ liệu đặc biệt dựa trên cấu trúc cây. Cây nhị phân được cho là tuân theo cấu trúc dữ liệu đống nếu

Nó là một cây nhị phân hoàn chỉnh.
Tất cả các nút trong cây tuân theo thuộc tính mà chúng lớn hơn phần tử con của chúng, tức là phần tử lớn nhất nằm ở nút gốc và các phần tử con của nó nhỏ hơn nút gốc,…. Một Heap như vậy được gọi là Max heap. Nếu thay vào đó, tất cả các nút đều nhỏ hơn nút con của chúng, nó được gọi là Min Heap.

Hình bên dưới đây sẽ minh họa về cấu trúc dữ liệu Max Heap và Min Heap.

Làm thế nào để để tạo một cấu trúc Heap cho một cây?

Bắt đầu từ một cây nhị phân hoàn chỉnh, chúng ta có thể sửa đổi nó để trở thành Max Heap bằng cách thực hiện một hàm có tên là Heapify trên tất cả các phần tử không phải là nút lá của Heap. Vì hàm Heapify sử dụng đệ quy nên có thể khó nắm bắt. Vì vậy, trước tiên chúng ta hãy nghĩ về cách ta sẽ tạo Heap cho một cây chỉ với ba phần tử.

heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)

heapify(array)

Root = array[0]

Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])

if(Root != Largest)

Swap(Root, Largest)

Ví dụ trên đưa ra 2 trường hợp, một trong số đó có nút gốc là phần tử lớn nhất và chúng ta không cần phải làm gì cả. Và một phần tử khác trong đó nút gốc có một nút con lớn hơn và chúng ta cần hoán đổi để duy trì thuộc tính Max Heap.

Nếu ta đã làm việc với các thuật toán đệ quy, ta có thể đã xác định rằng đây phải là trường hợp cơ sở (trường hợp để kết thúc lời gọi đệ quy).

Ví dụ 2:

Tuy nhiên, nút trên cùng không phải có cấu trúc Max Heap nhưng tất cả các cây con đều là Max Heap.

Để duy trì thuộc tính Max Heap cho toàn bộ cây, chúng ta sẽ phải tiếp tục đẩy 2 cây xuống dưới cho đến khi nó đến đúng vị trí của nó.

Do đó, để duy trì thuộc tính Max Heap trong một cây mà cả hai cây con đều là Max Heap, chúng ta cần thực hiện quá trình Heapify trên nút gốc nhiều lần cho đến khi nó lớn hơn cây con của nó hoặc nó trở thành một nút lá.

Chúng ta có thể kết hợp cả hai điều kiện này trong một hàm Heapify như sau:

void heapify(int arr[], int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;
  if (left < n && arr[left] > arr[largest])
    largest = left;
  if (right < n && arr[right] > arr[largest])
    largest = right;
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
  }
}

void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(&arr[i], &arr[largest]);

heapify(arr, n, largest);

}

Hàm này hoạt động hiệu quả cho trường hợp cơ sở và cho một cây có kích thước bất kỳ. Do đó, chúng ta có thể di chuyển nút gốc đến vị trí chính xác để duy trì trạng thái Max Heap cho bất kỳ kích thước cây nào miễn là các cây con có cấu trúc Max Heap.

Xây dựng cấu trúc Max heap

Để tạo Max Heap từ bất kỳ cây nào, ta có thể bắt đầu xếp từng cây con từ dưới lên và có được cấu trúc Max Heap sau khi hàm được áp dụng cho tất cả các phần tử bao gồm cả phần tử gốc.

Trong trường hợp của một cây hoàn chỉnh, chỉ số đầu tiên của một nút không phải nút lá được cho bởi n/2-1. Tất cả các nút khác sau đó là nút lá và do đó không cần phải tạo cấu trúc heap cho nó nữa.

Vì vậy, chúng ta có thể xây dựng một cấu trúc Max heap như sau:

for (int i = n / 2 - 1; i >= 0; i--)
   heapify(arr, n, i);

1 2	for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);

Như thể hiện trong sơ đồ trên, chúng ta sẽ bắt đầu bằng cách xếp vun đống cho các cây nhỏ nhất thấp nhất và dần dần di chuyển lên cho đến khi chúng ta đạt đến phần tử gốc.

Sắp xếp vun đống hoạt động như nào?

Vì cây thỏa mãn thuộc tính Max Heap, nên phần tử lớn nhất được lưu trữ tại nút gốc.
Hoán đổi: Loại bỏ phần tử gốc và đặt ở cuối mảng (vị trí thứ n). Đặt phần tử cuối cùng của cây (đống) vào chỗ trống.
Xóa: Giảm kích thước của Heap đi 1 đơn vị.
Heapify: Tạo cấu trúc Heap cho phần tử gốc để chúng ta có phần tử cao nhất ở nút gốc.
Quá trình này được lặp lại cho đến khi tất cả các phần tử của danh sách được sắp xếp.

Đoạn mã dưới đây sẽ đưa ra cách hoạt động.

for (int i = n - 1; i >= 0; i--) {
      swap(&arr[0], &arr[i]);
      // Heapify root element to get highest element at root again
      heapify(arr, i, 0);
}

for (int i = n - 1; i >= 0; i--) {

swap(&arr[0], &arr[i]);

// Heapify root element to get highest element at root again

heapify(arr, i, 0);

}

Ví dụ: Triển khai sắp xếp vun đống bằng ngôn ngữ lập trình C.

#include <stdio.h>
void swap(int *a, int *b) {
    int c = *a;
    *a = *b;
    *b = c;
}
  
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
      largest = left;
    if (right < n && arr[right] > arr[largest])
      largest = right;
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
    }
}

void sort_heap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
      swap(&arr[0], &arr[i]);
      heapify(arr, i, 0);
    }
}
  
void print(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {3, 14, 11, 7, 8, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    sort_heap(arr, n);
    printf("Mảng sau khi sắp xếp là: \n");
    print(arr, n);
}

#include <stdio.h>

void swap(int *a, int *b) {

int c = *a;

*a = *b;

*b = c;

}

void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(&arr[i], &arr[largest]);

heapify(arr, n, largest);

}

void sort_heap(int arr[], int n) {

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

for (int i = n - 1; i >= 0; i--) {

swap(&arr[0], &arr[i]);

heapify(arr, i, 0);

}

void print(int arr[], int n) {

for (int i = 0; i < n; ++i)

printf("%d ", arr[i]);

printf("\n");

}

int main() {

int arr[] = {3, 14, 11, 7, 8, 12};

int n = sizeof(arr) / sizeof(arr[0]);

sort_heap(arr, n);

printf("Mảng sau khi sắp xếp là: \n");

print(arr, n);

}

Kết quả:

Mảng sau khi sắp xếp là:
3 7 8 11 12 14

1 2	Mảng sau khi sắp xếp là: 3 7 8 11 12 14

Độ phức tạp của thuật toán sắp xếp vun đống

Heap Sort có độ phức tạp về thời gian là $O(n\;log\; n)$ cho tất cả các trường hợp (trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất).

Chiều cao của một cây nhị phân hoàn chỉnh chứa $n$ phần tử là $log \;n$

Như chúng ta đã thấy trước đó, để tạo cấu trúc Heap cho một phần tử có các cây con đã là Max Heap, chúng ta cần tiếp tục so sánh phần tử với các phần tử con bên trái và bên phải của nó và đẩy nó xuống dưới cho đến khi nó đạt đến điểm mà cả hai cây con của nó đều nhỏ hơn nó.

Trong trường hợp xấu nhất, chúng ta sẽ cần phải di chuyển một phần tử từ nút gốc đến nút lá để thực hiện nhiều phép so sánh và hoán đổi $log(n)$ .

Trong giai đoạn xây dựng cấu trúc Max Heap, chúng ta đã thực hiện điều đó cho $n/2$ phần tử nên độ phức tạp trong trường hợp xấu nhất của bước này là $n / 2 * log\; n \approx nlog\; n$ .

Trong bước sắp xếp, chúng ta hoán đổi phần tử gốc với phần tử cuối cùng và tạo cấu trúc Heap cho phần tử gốc. Đối với mỗi phần tử, điều này lại làm tốn thời gian là $log\; n$ vì chúng ta có thể phải đưa phần tử đó từ nút gốc đến nút lá. Vì chúng ta lặp lại n lần này nên bước sắp xếp vun đống cũng là $nlog\;n$ .

Cũng vì các bước xây dựng cấu trúc Max Heap và sắp xếp vun đống được thực hiện lần lượt nên độ phức tạp của thuật toán không được nhân lên và nó vẫn theo thứ tự $nlog\;n$ .

Ngoài ra, nó thực hiện sắp xếp theo độ phức tạp về không gian là $O(1)$ . So với Sắp xếp nhanh, nó có trường hợp xấu nhất tốt hơn là $(O(nlog\;n))$ . Sắp xếp nhanh có độ phức tạp $O(n^{2})$ cho trường hợp xấu nhất. Nhưng trong các trường hợp khác, thuật toán sắp xếp nhanh hay QuickSort sẽ nhanh hơn.

Ứng dụng của thuật toán sắp xếp vun đống

Các hệ thống liên quan đến bảo mật và các hệ thống nhúng như nhân Linux sử dụng thuật toán sắp xếp vun đống vì giới hạn trên là $O(n log \;n)$ cho thời gian chạy của HeapSort và giới hạn trên không đổi là $O(1)$ cho bộ nhớ phụ của nó.

Mặc dù HeapSort có độ phức tạp về thời gian là $O(nlog\;n)$ ngay cả trong trường hợp xấu nhất, nó không có nhiều ứng dụng (so với các thuật toán sắp xếp khác như QuickSort, MergeSort). Tuy nhiên, cấu trúc dữ liệu cơ bản của nó, Heap, có thể được sử dụng hiệu quả nếu chúng ta muốn trích xuất phần nhỏ nhất (hoặc lớn nhất) từ danh sách các phần tử mà không cần phải giữ các phần tử còn lại theo thứ tự đã sắp xếp. Ví dụ như hàng đợi ưu tiên.

Trên đây là khái niệm và ví dụ cơ bản về thuật toán sắp xếp vun đống. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!

P/s: Cảm ơn mọi người đã tin tưởng tek4!

Bài trước: Thuật toán sắp xếp theo khối (Bucket Sort)

Bài tiếp theo: Shell Sort (ứng dụng của sắp xếp chèn)

0 0 vote

Article Rating