Giới thiệu về thuật toán Heap sort và ví dụ minh họa

Heap sort: Một cách để sắp xếp dữ liệu

Thuật toán Heap sort là một trong những phương pháp sắp xếp phổ biến dựa trên cấu trúc dữ liệu Heap. Heap sort giúp sắp xếp các phần tử trong danh sách theo thứ tự tăng dần và nói chung không quá phức tạp.

Thuật toán Heap sort là gì?

Thuật toán Heap sort sử dụng cấu trúc dữ liệu Binary Heap để sắp xếp các phần tử. Cấu trúc dữ liệu Heap là một cây nhị phân đầy đủ và thỏa mãn thuộc tính heap. Heap sort sắp xếp các phần tử sao cho phần tử lớn nhất luôn được xếp ở cuối danh sách. Quá trình này lặp lại cho từng phần tử còn lại trong danh sách.

Bạn đang xem: Giới thiệu về thuật toán Heap sort và ví dụ minh họa

Heap sort được lựa chọn vì tốc độ chạy nhanh và đơn giản. Điều này làm cho nó trở thành một trong những thuật toán sắp xếp phổ biến trong lập trình.

Cấu trúc dữ liệu Heap

Cấu trúc dữ liệu Heap là một cây nhị phân đầy đủ và được biểu diễn dưới dạng mảng. Cây nhị phân này có một cấu trúc đặc biệt, gồm hai loại:

• Max heap: Phần tử trong nút cha luôn lớn hơn tất cả các phần tử trong nút con, và giá trị nút gốc là lớn nhất.

• Xem thêm : Nỗ Lực Là Gì? Cách Nỗ Lực Để Giúp Cuộc Sống Thành Công Như Mong Muốn!

  Min heap: Phần tử trong nút cha luôn nhỏ hơn tất cả các phần tử trong nút con, và giá trị nút gốc là nhỏ nhất.

Cấu trúc dữ liệu Heap được sử dụng để biểu diễn và duy trì thuộc tính heap của một nút trong cây nhị phân.

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 thuật toán Heapify. Thuật toán này được sử dụng để biến một cây nhị phân đầy đủ thành Max heap bằng cách sắp xếp các phần tử không phải là nút lá của Heap.

Trong ví dụ dưới đây, chúng ta sẽ tạo cấu trúc dữ liệu Heap cho một cây nhị phân với 3 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)

Kết quả đạt được là cây nhị phân có phần tử gốc lớn nhất.

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:

1. Xem thêm : 100 slogan học tập, khẩu hiệu cỗ vũ tinh thần học tập

   Phần tử lớn nhất được đặt ở nút gốc theo thuộc tính Max Heap.

2. Loại bỏ phần tử gốc và đặt nó vào cuối danh sách. Đồng thời, giảm kích thước của Heap đi 1.

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

4. Lặp lại quá trình trên cho đến khi tất cả các phần tử trong danh sách được sắp xếp đúng.

Dưới đây là một ví dụ về hoạt động của thuật toán Heap sort:

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

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về thuật toán Heap sort và cách nó hoạt động. Heap sort là một phương pháp sắp xếp dữ liệu đơn giản và hiệu quả dựa trên cấu trúc dữ liệu Heap. Chun

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập