Heap Sort (Sắp xếp đống) trong Python là gì?

Heap Sort là kỹ thuật sắp xếp dựa trên cấu trúc dữ liệu binary heap (đống nhị phân). Để hiểu heap sort, bạn cần quen với cây nhị phân (binary tree) và binary heap.

Cây nhị phân hoàn chỉnh (Complete binary tree) là gì?

Cây nhị phân hoàn chỉnh là cấu trúc cây nơi mọi cấp độ đều đầy đủ, trừ cấp độ cuối cùng được lấp đầy từ trái sang phải.

Binary heap là gì?

Binary heap là trường hợp đặc biệt của cây nhị phân. Có hai loại:

• Max Heap – nút cha lớn hơn nút con tại mỗi cấp.
• Min Heap – nút cha nhỏ hơn nút con tại mỗi cấp.

Biểu diễn mảng của cây nhị phân hoàn chỉnh

Binary heap có thể biểu diễn bằng mảng vì tiết kiệm không gian. Nếu nút cha ở chỉ số i, con trái = 2*i + 1, con phải = 2*i + 2 (chỉ số từ 0).

Thuật toán Heap Sort

• Xây dựng max heap từ cây nhị phân hoàn chỉnh.
• Loại bỏ gốc (root), thay bằng phần tử cuối heap, giảm size heap 1, xây lại max heap từ các nút còn lại.
• Lặp lại bước 2 cho đến khi chỉ còn 1 nút.

Xây dựng max heap từ cây nhị phân hoàn chỉnh

Mã sau xây dựng max heap: so sánh hai con với gốc, nếu phần tử lớn hơn không phải gốc thì hoán đổi với gốc. Quy trình đệ quy: gốc hiện tại nhỏ hơn con thì tiếp tục so sánh với các cây con thấp hơn cho đến vị trí đúng.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

Heap Sort

Sau khi có max heap, thực hiện:

• Hoán đổi gốc với phần tử cuối heap.
• Giảm size heap 1 (phần tử lớn nhất đã về đúng vị trí cuối).
• Xây lại max heap bỏ qua phần tử cuối.
• Lặp lại cho đến khi còn 1 phần tử.

for i in range(n-1, 0, -1):
    arr[i], arr[0] = arr[0], arr[i]
    heapify(arr, i, 0)

Chương trình hoàn chỉnh heap sort trong Python:

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    # Build max heap
    for i in range(n//2, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
    print(arr[i], end=' ')

ĐỘ PHỨC TẠP THỜI GIAN - O(n log n)