Chương trình C++ sắp xếp mảng 10 phần tử bằng thuật toán Heap Sort

Heap Sort (sắp xếp vun đống) dựa trên cấu trúc dữ liệu binary heap (đống nhị phân). Trong max heap, các nút con luôn nhỏ hơn hoặc bằng nút cha; trong min heap thì ngược lại, nút con lớn hơn hoặc bằng nút cha.

Dưới đây là ví dụ minh họa đầy đủ các bước của Heap Sort:

Mảng gốc 10 phần tử trước khi sắp xếp:

Mảng này được xây dựng thành max heap bằng hàm max-heapify. Max heap biểu diễn dưới dạng mảng:

Phần tử gốc của max heap được lấy ra và đặt vào cuối mảng. Sau đó gọi max heapify để chuyển phần còn lại thành max heap. Quá trình lặp lại cho đến khi mảng được sắp xếp hoàn toàn:

Chương trình sắp xếp mảng 10 phần tử bằng Heap Sort:

Ví dụ

#include <iostream>
using namespace std;

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

void heapSort(int arr[], int n) {
  int temp;
  // Xây dựng max heap từ các nút không phải lá
  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);
  // Trích xuất phần tử từ heap từng cái một
  for (int i = n - 1; i >= 0; i--) {
    temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}

int main() {
  int arr[] = {20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
  int n = 10;
  int i;
  
  cout << "Mảng ban đầu: " << endl;
  for (i = 0; i < n; i++)
    cout << arr[i] << " ";
  cout << endl;
  
  heapSort(arr, n);
  
  printf("\nMảng đã sắp xếp: \n");
  for (i = 0; i < n; ++i)
    cout << arr[i] << " ";
}

Kết quả đầu ra

Mảng ban đầu: 20 7 1 54 10 15 90 23 77 25
Mảng đã sắp xếp: 1 7 10 15 20 23 25 54 77 90

Trong chương trình trên, hàm heapify() chuyển đổi các phần tử thành heap. Đây là hàm đệ quy tạo max heap bắt đầu từ phần tử được gọi (i). Đoạn mã minh họa:

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

Hàm heapSort() sắp xếp mảng bằng heap sort. Nó bắt đầu từ các nút không phải lá và gọi heapify() trên từng nút, chuyển mảng thành binary max heap:

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

Sau đó, heapSort() lấy phần tử gốc mỗi vòng lặp và đặt vào cuối mảng, rồi gọi heapify() để đảm bảo phần còn lại vẫn là max heap. Cuối cùng tất cả phần tử được lấy ra khỏi max heap và mảng đã sắp xếp được tạo thành:

for (int i = n - 1; i >= 0; i--) {
  temp = arr[0];
  arr[0] = arr[i];
  arr[i] = temp;
  heapify(arr, i, 0);
}

Trong hàm main(), mảng được hiển thị trước, sau đó gọi heapSort() để sắp xếp:

cout << "Mảng ban đầu: " << endl;
for (i = 0; i < n; i++)
  cout << arr[i] << " ";
cout << endl;
heapSort(arr, n);

Cuối cùng, mảng đã sắp xếp được hiển thị:

printf("\nMảng đã sắp xếp: \n");
for (i = 0; i < n; ++i)
  cout << arr[i] << " ";