Chương trình Python Heap Sort

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho một mảng, cần sắp xếp dùng Heap Sort.

Đặt phần tử lớn nhất ở cuối. Lặp lại cho đến khi mảng sắp xếp xong.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# heapify
def heapify(arr, n, i):
    largest = i  # giá trị lớn nhất
    l = 2 * i + 1  # trái
    r = 2 * i + 2  # phải
    # nếu con trái tồn tại và lớn hơn gốc
    if l < n and arr[i] < arr[l]:
        largest = l
    # nếu con phải tồn tại và lớn hơn largest
    if r < n and arr[largest] < arr[r]:
        largest = r
    # nếu gốc không phải largest
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        heapify(arr, n, largest)

# sort
def heapSort(arr):
    n = len(arr)
    # xây max heap
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    # trích xuất phần tử
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)

# main
arr = [2, 5, 3, 8, 6, 5, 4, 7]
heapSort(arr)
n = len(arr)
print("Mảng đã sắp xếp:")
for i in range(n):
    print(arr[i], end=" ")

Kết quả

Mảng đã sắp xếp: 2 3 4 5 5 6 7 8

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python Heap Sort.