×

Cài đặt thuật toán Heap Sort trong lập trình

Avatar of admin
admin 0 Views

Heap Sort là một thuật toán sắp xếp hiệu quả với độ phức tạp O(n log n), được sử dụng rộng rãi trong nhiều ứng dụng khác nhau. Dưới đây là mô tả chi tiết về cách cài đặt thuật toán này trong lập trình.

1. Khái niệm cơ bản về Heap Sort

Heap Sort tận dụng cấu trúc dữ liệu Heap, một dạng cây nhị phân gần như đầy đủ, để tổ chức lại các phần tử trong mảng. Có hai loại Heap chính: Max-Heap (nơi phần tử lớn nhất nằm ở gốc) và Min-Heap (nơi phần tử nhỏ nhất nằm ở gốc). Heap Sort thường được triển khai bằng Max-Heap để sắp xếp theo thứ tự tăng dần.

2. Các bước thực hiện

Thuật toán Heap Sort gồm hai giai đoạn chính:

  1. Xây dựng Max-Heap từ mảng đầu vào.
  2. Thực hiện quá trình sắp xếp bằng cách liên tục đưa phần tử gốc của Max-Heap đến cuối mảng và điều chỉnh lại Heap.

Bước 1: Xây dựng Max-Heap

Quá trình này xây dựng một Heap từ mảng đầu vào. Ý tưởng chính là bắt đầu từ những node không phải là lá, điều chỉnh mỗi node để đảm bảo thuộc tính Max-Heap được duy trì.

def heapify(arr, n, i):
    largest = i # Khởi tạo largest như root
    l = 2 * i + 1 # con trái = 2*i + 1
    r = 2 * i + 2 # con phải = 2*i + 2

    # Kiểm tra nếu con trái của root tồn tại và lớn hơn root
    if l < n and arr[i] < arr[l]:
        largest = l

    # Kiểm tra nếu con phải của root tồn tại và lớn hơn largest
    if r < n and arr[largest] < arr[r]:
        largest = r

    # Nếu largest không phải root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i] # hoán đổi

        # Đệ quy heapify lại cho node bị ảnh hưởng
        heapify(arr, n, largest)

Bước 2: Thực hiện quá trình sắp xếp

Sau khi xây dựng được Max-Heap, ta có thể tiến hành sắp xếp bằng cách đưa phần tử lớn nhất (ở gốc Heap) đến cuối mảng, thu nhỏ kích thước của Heap và điều chỉnh lại Heap để duy trì thuộc tính Max-Heap.

def heap_sort(arr):
    n = len(arr)

    # Xây dựng Max-Heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Một một phần tử từng phần một & điều chỉnh heap
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i] # hoán đổi
        heapify(arr, i, 0)

3. Ví dụ minh họa

Giả sử chúng ta có một mảng arr = [12, 11, 13, 5, 6, 7] và cần sắp xếp nó bằng thuật toán Heap Sort:

if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]
    heap_sort(arr)
    print("Mảng đã sắp xếp là:", arr)

Kết quả sẽ là:

Mảng đã sắp xếp là: [5, 6, 7, 11, 12, 13]

4. Ưu và nhược điểm

Ưu điểm:

  1. Hiệu quả với độ phức tạp O(n log n).
  2. Không cần bộ nhớ phụ, vì nó là một thuật toán sắp xếp tại chỗ.

Nhược điểm:

  1. Hiệu suất trung bình chậm hơn so với Quick Sort trong các trường hợp cụ thể.
  2. Cấu trúc cây nhị phân sử dụng có thể khó hiểu với người mới bắt đầu.

5. Kết luận

Heap Sort là một thuật toán sắp xếp mạnh mẽ với khả năng xử lý tốt các mảng lớn mà không cần thêm bộ nhớ phụ. Hiểu và cài đặt đúng thuật toán này giúp cải thiện hiệu quả lập trình, tiết kiệm bộ nhớ và tăng hiệu quả xử lý dữ liệu. Hãy thử áp dụng và tối ưu hóa nó để nắm vững các khái niệm liên quan đến cấu trúc dữ liệu và thuật toán.

Comments

Bài viết liên quan