Heap Sort (Sắp Xếp Vun Đống)

Heap Sort biến mảng thành một cấu trúc dữ liệu gọi là Binary Heap (thường là Max-Heap), sau đó liên tục lấy phần tử lớn nhất (gốc của Heap) ra để xếp vào cuối mảng.

Cơ Chế Hoạt Động

1. Build Heap: Biến mảng đầu vào thành một Max-Heap (Phần tử cha luôn lớn hơn các con). Lúc này, phần tử lớn nhất (arr[0]) nằm ở đỉnh.
2. Extract Max:
   • Hoán đổi arr[0] với phần tử cuối cùng của Heap.
   • Giảm kích thước Heap đi 1.
   • Thực hiện Heapify (vun lại đống) cho phần tử gốc mới để đảm bảo tính chất Max-Heap.
   • Lặp lại.

Code Implementation

Phần khó nhất là hàm heapify.

C++

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1; // Con trái
    int r = 2 * i + 2; // Con phải

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Java

class HeapSort {
    void heapify(int arr[], int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }

    void sort(int arr[]) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

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

Python

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    # Build a maxheap.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

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

🎓 HPN's Comparison: Quick Sort vs Heap Sort

Cả hai đều có độ phức tạp trung bình là O(N log N). Tuy nhiên, Quick Sort thường chạy nhanh hơn trong thực tế. Tại sao? Đó là do Cache Locality (Tính cục bộ của bộ nhớ). Quick Sort duyệt qua mảng theo tuần tự (gần nhau trong bộ nhớ), trong khi Heap Sort nhảy lung tung giữa i, 2*i+1, 2*i+2. CPU Cache cực ghét việc nhảy cóc này!