Cấu trúc dữ liệu Heap có nhiều ứng dụng quan trọng trong các thuật toán. Dưới đây là cách sử dụng Heap để sắp xếp mảng và giải quyết vấn đề Top-K.

1. Thuật toán sắp xếp Heap

Để xây dựng một Heap từ mảng, chúng ta cần điều chỉnh các phần tử sao cho thỏa mãn tính chất của Heap. Ví dụ với mảng sau:

int mang[] = {4, 2, 8, 1, 5, 6, 9, 7, 3};

Chúng ta có thể xây dựng Heap tăng dần bằng cách điều chỉnh từng phần tử theo thứ tự từ cuối về đầu:

void dieu_chinh_len(int arr[], int vi_tri, int so_phan_tu) {
    while (vi_tri > 0) {
        int cha = (vi_tri - 1) / 2;
        if (arr[vi_tri] <= arr[cha]) break;
        swap(arr[vi_tri], arr[cha]);
        vi_tri = cha;
    }
}

int main() {
    int mang[] = {4, 2, 8, 1, 5, 6, 9, 7, 3};
    int n = sizeof(mang) / sizeof(mang[0]);

    for (int i = 1; i < n; ++i) {
        dieu_chinh_len(mang, i, n);
    }

    return 0;
}

Sau khi có Heap, chúng ta có thể sắp xếp mảng theo thứ tự tăng dần bằng cách hoán đổi phần tử đầu với phần tử cuối và tiếp tục điều chỉnh lại Heap:

void dieu_chinh_xuong(int arr[], int vi_tri, int heap_size) {
    int con_trai = 2 * vi_tri + 1;
    int con_phai = 2 * vi_tri + 2;
    int lon_nhat = vi_tri;

    if (con_trai < heap_size && arr[con_trai] > arr[lon_nhat])
        lon_nhat = con_trai;

    if (con_phai < heap_size && arr[con_phai] > arr[lon_nhat])
        lon_nhat = con_phai;

    if (lon_nhat != vi_tri) {
        swap(arr[vi_tri], arr[lon_nhat]);
        dieu_chinh_xuong(arr, lon_nhat, heap_size);
    }
}

void sap_xep_heap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; --i)
        dieu_chinh_xuong(arr, i, n);

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

2. Độ phức tạp thời gian

• Điều chỉnh lên: Mỗi lần điều chỉnh có thể đi qua tối đa log(N) cấp độ của cây, dẫn đến tổng độ phức tạp O(N log N).
• Điều chỉnh xuống: Tổng số lần di chuyển các phần tử ít hơn, dẫn đến hiệu suất tốt hơn với độ phức tạp O(N).

3. Giải quyết bài toán Top-K

Bài toán tìm K phần tử lớn nhất/nhỏ nhất trong tập hợp dữ liệu lớn có thể được giải quyết hiệu quả bằng Heap:

void tim_top_k(int arr[], int n, int k, int ket_qua[]) {
    // Xây dựng Min-Heap với k phần tử đầu tiên
    for (int i = k / 2 - 1; i >= 0; --i)
        dieu_chinh_xuong(arr, i, k);

    // So sánh các phần tử còn lại với đỉnh Heap
    for (int i = k; i < n; ++i) {
        if (arr[i] > arr[0]) {
            arr[0] = arr[i];
            dieu_chinh_xuong(arr, 0, k);
        }
    }

    // Sao chép kết quả
    for (int i = 0; i < k; ++i)
        ket_qua[i] = arr[i];
}

Thuật toán này có độ phức tạp O(N), phù hợp cho việc xử lý dữ liệu lớn mà không cần sắp xếp toàn bộ.