Heap sort - sắp xếp vun đống

1. Giới thiệu

Heap sort là một kỹ thuật sắp xếp dựa trên so sánh dựa trên cấu trúc dữ liệu Binary Heap. Nó tương tự như sắp xếp lựa chọn, nơi đầu tiên chúng ta tìm phần tử lớn nhất và đặt phần tử lớn nhất ở cuối. Chúng ta lặp lại quá trình tương tự cho các phần tử còn lại.

Một Binary Heap là một cây nhị phân hoàn chỉnh trong đó các mục được lưu trữ theo một thứ tự đặc biệt sao cho giá trị trong nút cha lớn hơn (hoặc nhỏ hơn) so với giá trị trong hai nút con của nó. Cái trước được gọi là max heap và cái sau được gọi là min-heap. Heap có thể được biểu diễn bằng một cây hoặc mảng nhị phân.

Tại sao biểu diễn dựa trên mảng cho Binary Heap?

Vì một Binary Heap là một cây nhị phân hoàn chỉnh, nó có thể dễ dàng được biểu diễn dưới dạng một mảng và biểu diễn dựa trên mảng là không gian hiệu quả. Nếu nút cha được lưu trữ ở chỉ mục i, nút con bên trái có thể được tính bằng 2 * i + 1 và nút con bên phải bằng 2 * i + 2 (giả sử việc lập chỉ mục bắt đầu từ 0).

Thuật toán Heap Sort được dùng để sắp xếp theo thứ tự tăng dần:

• Xây dựng một heap tối đa từ dữ liệu đầu vào.
• Tại thời điểm này, mục lớn nhất được lưu trữ ở gốc của heap. Thay thế nó bằng mục cuối cùng của heap, sau đó giảm kích thước của heap đi 1. Cuối cùng, heap được “vun đống”.
• Lặp lại bước 2 trong khi kích thước của đống lớn hơn 1.

Biểu diễn Heap dưới dạng mảng, ta có:

• Gốc của cây là A[1]
• Con trái của A[i] là A[2i]*
• Con phải của A[i] là A[2i+1]*
• Cha của A[i] là A[ i/2 ]
• Số lượng phần tử của heap là Heapsize[A] ≤ length[A]

Phân loại: Có 2 loại

• Max-heaps (Phần tử lớn nhất ở gốc): với mọi nút i, ngoại trừ gốc: A[parent(i)] ≥ A[i]
• Min-heaps (Phần tử nhỏ nhất ở gốc): với mọi nút i, ngoại trừ gốc: A[parent(i)] ≤ A[i]

2. Làm thế nào để xây dựng Heap?

Thủ tục Heapify chỉ có thể được áp dụng cho một nút nếu các nút con của nó được “vun đống”. Vì vậy việc vun đống phải được thực hiện theo thứ tự từ dưới lên.

Hãy hiểu rõ hơn thông qua ví dụ sau:

# Dữ liệu đầu vào: 4, 10, 3, 5, 1

         4(0)
        /   \
     10(1)   3(2)
    /   \
 5(3)    1(4)

// Các số trong ngoặc biểu thị các chỉ số trong mảng biểu diễn dữ liệu.
# Áp dụng quy trình heapify cho chỉ mục 1:

         4(0)
        /   \
    10(1)    3(2)
    /   \
5(3)    1(4)

# Áp dụng quy trình heapify cho chỉ mục 0:

        10(0)
        /  \
     5(1)  3(2)
    /   \
 4(3)    1(4)

# Thủ tục heapify tự gọi đệ quy để xây dựng heap theo cách từ trên xuống.

3. Code demo

Từ ví dụ ở mục 2, chúng ta dễ dàng chuyển chúng thành code – có nội dung như bên dưới.

public class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;

        // Xây dựng Heap (sắp xếp lại mảng)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // Trích xuất từng phần tử từ Heap
        for (int i = n - 1; i > 0; i--) {
            // Di chuyển root hiện tại đến end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // gọi max - heapify trên Heap đã sắp xếp
            heapify(arr, i, 0);
        }
    }

    // Để vun đống một cây con bắt nguồn từ nút i là
    // một chỉ mục trong arr[]. n là kích thước của Heap
    void heapify(int arr[], int n, int i) {
        int largest = i; // Khởi tạo largest như root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2

        // Nếu nút con bên trái lớn hơn nút con của gốc
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // Nếu nút con bên phải lớn hơn largest
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // Nếu largest không phải là root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Vun đống lại các cây con bị ảnh hưởng
            heapify(arr, n, largest);
        }
    }

    // In mảng kích thước n
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {4, 10, 3, 5, 1};
        int n = arr.length;

        System.out.println("Mảng ban đầu:");
        printArray(arr);

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        System.out.println("Mảng sau khi sắp xếp:");
        printArray(arr);
    }
}

Ghi chú:

• Heap sort là một thuật toán in-place - Việc triển khai điển hình của nó không ổn định.
• Độ phức tạp về thời gian của heapify là O(Logn). Độ phức tạp thời gian của createAndBuildHeap() là O(n) và độ phức tạp thời gian tổng thể của Heap Sort là O(nLogn).

Heap sort có hạn chế sử dụng vì Quick-sort và Merge-sort tốt hơn trong thực tế. Tuy nhiên, bản thân cấu trúc dữ liệu Heap được sử dụng rất nhiều, do đó việc tìm hiểu và ứng dụng tốt HeapSort không phải là chuyện dư thừa.

Bổ sung hoặc cập nhật sớm sẽ giúp bạn có thêm nhiều lựa chọn giải quyết các vấn đề trong các bài tập thức tế, đặc biệt liên quan đến cấu trúc dữ liệu Heap.

Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!

Happy coding! 😎 👍🏻 🚀 🔥