Thuật toán Heap Sort và ví dụ minh họa: Bí quyết sắp xếp nhanh chóng

Trong lĩnh vực lập trình, các thuật toán sắp xếp đóng vai trò quan trọng trong việc xử lý dữ liệu. Một thuật toán sắp xếp nổi tiếng và được ưa chuộng là Heap Sort. Hôm nay, Izumi.Edu.VN sẽ giới thiệu về thuật toán này cùng ví dụ minh họa để bạn có thể thực hiện những công việc sắp xếp dữ liệu nhanh chóng.

1. Heap Sort là gì?

Heap Sort là một thuật toán sắp xếp dựa trên cấu trúc dữ liệu Binary Heap. Thuật toán này giúp sắp xếp các phần tử trong danh sách sao cho phần tử lớn nhất được đặt ở cuối danh sách, và quá trình này được lặp lại cho các phần tử còn lại trong danh sách. Heap Sort được lựa chọn sử dụng nhiều nhờ tốc độ chạy nhanh và không quá phức tạp.

Bạn đang xem: Thuật toán Heap Sort và ví dụ minh họa: Bí quyết sắp xếp nhanh chóng

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

Heap là cấu trúc dữ liệu đặc biệt dựa trên một cây nhị phân hoàn chỉnh và thỏa mãn thuộc tính heap. Một cây nhị phân có các phần tử được lưu trữ theo một thứ tự đặc biệt. Trong thuật toán Heap Sort, Heap được sử dụng để biểu diễn thuộc tính heap của một nút trong cây nhị phân. Có hai loại Heap là Max Heap và Min Heap.

3. Tạo cấu trúc dữ liệu Heap cho một cây nhị phân

Để tạo cấu trúc dữ liệu Heap cho một cây nhị phân, chúng ta sử dụng một số thuật toán như Heapify. Ví dụ minh họa dưới đây cho thấy quá trình tạo cấu trúc dữ liệu Heap cho một cây nhị phân:

4. Hoạt động của thuật toán Heap Sort

Thuật toán Heap Sort hoạt động theo các nguyên tắc sau:

• Phần tử lớn nhất được đặt ở nút gốc theo thuộc tính Max Heap.
• Loại bỏ phần tử gốc và đặt nó vào cuối mảng.
• Giảm kích thước của Heap đi 1 đơn vị.
• Tạo cấu trúc dữ liệu Heap cho phần tử gốc để nút gốc chứa phần tử có giá trị lớn nhất.
• Lặp lại quá trình này cho đến khi tất cả các phần tử của danh sách được sắp xếp đúng.

Dưới đây là minh họa cho quá trình hoạt động của thuật toán Heap Sort:

Thông qua đoạn mã dưới đây, bạn có thể hiểu rõ hơn về cách hoạt động của thuật toán Heap Sort:

#include 

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ả nhận được:

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

Thông qua bài viết này, Izumi.Edu.VN đã giới thiệu cơ bản về thuật toán Heap Sort và ví dụ minh họa. Hy vọng rằng bạn sẽ áp dụng đúng các nguyên tắc này vào chương trình của mình.

Izumi.Edu.VN là tổ chức giáo dục trực tuyến uy tín, chuyên đào tạo các khóa học Công nghệ thông tin từ cơ bản đến nâng cao. Hãy khám phá các khóa học của chúng tôi tại Izumi.Edu.VN để nắm bắt kiến thức mới nhất và nâng cao kỹ năng lập trình của bạn.

Nguồn: https://izumi.edu.vn/
Danh mục: Tài liệu toán