Bài 15.2. Heap và cấu trúc dữ liệu heap

Chào mừng các bạn đã quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Sau khi khám phá các cấu trúc tuyến tính và một số dạng cây cơ bản, hôm nay chúng ta sẽ đi sâu vào một loại cây đặc biệt, có sức mạnh đáng kinh ngạc trong việc quản lý các yếu tố dựa trên độ ưu tiên hoặc giá trị lớn nhất/nhỏ nhất: đó chính là Heap.

Heap không chỉ là một cấu trúc dữ liệu thú vị về mặt lý thuyết, mà còn là nền tảng cho nhiều thuật toán quan trọng và được sử dụng rộng rãi trong các ứng dụng thực tế, đặc biệt là trong việc triển khai Priority Queue (Hàng đợi ưu tiên) và thuật toán Heap Sort. Hãy cùng nhau khám phá sức mạnh và sự hiệu quả của Heap nhé!

Heap là gì? Các đặc tính cốt lõi

Về bản chất, Heap là một cây nhị phân (binary tree) tuân thủ hai thuộc tính chính:

Thuộc tính cây nhị phân đầy đủ (Complete Binary Tree Property): Tất cả các mức (level) của cây đều được lấp đầy hoàn toàn, ngoại trừ có thể là mức cuối cùng. Nếu mức cuối cùng không đầy đủ, các nút (node) phải được lấp từ trái sang phải. Thuộc tính này cực kỳ quan trọng vì nó cho phép chúng ta biểu diễn Heap một cách hiệu quả bằng mảng (array) mà không cần dùng con trỏ.
Thuộc tính Heap (Heap Property): Đây là đặc tính quan trọng nhất định nghĩa Heap. Nó quy định mối quan hệ giữa giá trị của nút cha (parent) và các nút con (children). Có hai loại Heap chính dựa trên thuộc tính này:
- Max Heap: Đối với mọi nút i (trừ nút gốc), giá trị của nút cha i phải lớn hơn hoặc bằng giá trị của nút con của nó. Nói cách khác, phần tử lớn nhất luôn nằm ở nút gốc.
- Min Heap: Đối với mọi nút i (trừ nút gốc), giá trị của nút cha i phải nhỏ hơn hoặc bằng giá trị của nút con của nó. Nói cách khác, phần tử nhỏ nhất luôn nằm ở nút gốc.

Trong bài viết này, chúng ta sẽ tập trung chủ yếu vào Max Heap để minh họa, nhưng các nguyên lý và thao tác hoàn toàn tương tự với Min Heap.

Biểu diễn Heap bằng Mảng

Như đã đề cập, nhờ thuộc tính cây nhị phân đầy đủ, Heap có thể được biểu diễn một cách thanh lịch và hiệu quả bằng một mảng hoặc vector. Chúng ta chỉ cần lưu trữ các phần tử của cây theo thứ tự duyệt duyệt theo mức (level order traversal).

Với cách biểu diễn này (thường dùng mảng 0-based index), mối quan hệ giữa các nút trở nên rất đơn giản thông qua các công thức chỉ số:

Nếu một nút ở chỉ số i, thì:
- Nút cha của nó (trừ gốc i=0) nằm ở chỉ số: (i - 1) / 2
- Nút con trái của nó nằm ở chỉ số: 2 * i + 1
- Nút con phải của nó nằm ở chỉ số: 2 * i + 2

Việc sử dụng mảng giúp tiết kiệm bộ nhớ (không cần lưu con trỏ) và cải thiện hiệu suất truy cập. Kích thước của Heap chính là số lượng phần tử hiện có trong mảng.

Các Thao tác Cơ bản trên Heap

Để Heap thực sự hữu ích, chúng ta cần các thao tác để thêm phần tử, xóa phần tử (thường là phần tử ưu tiên nhất ở gốc) và duy trì thuộc tính Heap sau mỗi thao tác. Hai thao tác chính để duy trì thuộc tính Heap là Heapify (siftDown) và SiftUp (bubbleUp).

1. Thao tác `Heapify` (hay `siftDown` / `bubbleDown`)

Thao tác này được sử dụng để khôi phục lại thuộc tính Heap tại một nút cụ thể, giả sử rằng các cây con của nó đã là Heap. Nó hoạt động bằng cách đẩy (sift down) một phần tử từ một vị trí xuống phía dưới để tìm vị trí đúng của nó trong cây con. Thao tác này thường được gọi sau khi xóa gốc hoặc khi xây dựng Heap từ một mảng.

Mục đích: Đảm bảo nút tại chỉ số i và cây con của nó thỏa mãn thuộc tính Heap, giả sử rằng các cây con của các nút con của i đã là Heap hợp lệ.
Cách hoạt động (với Max Heap):
1. Bắt đầu tại chỉ số i.
2. So sánh giá trị của nút i với giá trị của hai nút con của nó (nếu tồn tại).
3. Tìm chỉ số của nút có giá trị lớn nhất trong ba nút (nút i, con trái, con phải).
4. Nếu nút i không phải là nút lớn nhất trong ba, hoán đổi giá trị của nút i với nút lớn nhất đó.
5. Sau khi hoán đổi, thuộc tính Heap có thể bị vi phạm tại vị trí mới của phần tử ban đầu ở nút i. Do đó, chúng ta đệ quy gọi lại heapify trên chỉ số của nút đã bị hoán đổi.
6. Quá trình dừng lại khi nút i là nút lớn nhất trong ba, hoặc khi nó không còn nút con (là nút lá).
Code minh họa heapify trong C++ (cho Max Heap):

#include <vector>
#include <iostream>
#include <algorithm> // Để sử dụng std::swap

// Hàm heapify để duy trì thuộc tính Max Heap
// n: kích thước hiện tại của heap
// i: chỉ số của nút cần heapify (gốc của cây con cần xem xét)
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i; // Khởi tạo largest là root
    int left_child = 2 * i + 1; // Chỉ số con trái
    int right_child = 2 * i + 2; // Chỉ số con phải

    // So sánh root với con trái
    if (left_child < n && arr[left_child] > arr[largest]) {
        largest = left_child;
    }

    // So sánh largest hiện tại với con phải
    if (right_child < n && arr[right_child] > arr[largest]) {
        largest = right_child;
    }

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

        // Tiếp tục heapify cây con bị ảnh hưởng
        heapify(arr, n, largest);
    }
}

// Hàm hỗ trợ để in vector (heap)
void printHeap(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Example usage (trong hàm main hoặc riêng)
/*
int main() {
    std::vector<int> myHeap = {10, 5, 3, 2, 4}; // Ví dụ ban đầu
    int n = myHeap.size();
    int root_to_heapify = 0; // Heapify từ gốc

    std::cout << "Before heapify: ";
    printHeap(myHeap);

    // Giả sử ta cần heapify từ gốc (ví dụ này hơi đơn giản vì nó đã là heap)
    // Một ví dụ khác: nếu ta thay đổi gốc {1, 5, 3, 2, 4}
    // myHeap = {1, 5, 3, 2, 4};
    // n = myHeap.size();
    // heapify(myHeap, n, 0); // Kết quả sẽ là {5, 4, 3, 2, 1} (chưa đúng lắm, vì đây là Max Heap)
    // Để minh họa tốt hơn: {1, 9, 8, 5, 7} -> heapify(0) -> {9, 7, 8, 5, 1}
    myHeap = {1, 9, 8, 5, 7};
    n = myHeap.size();
    std::cout << "Before heapify(0) on {1, 9, 8, 5, 7}: ";
    printHeap(myHeap);
    heapify(myHeap, n, 0);
    std::cout << "After heapify(0): ";
    printHeap(myHeap); // Output: 9 7 8 5 1

    return 0;
}
*/

Giải thích code heapify:
- Hàm nhận vào vector arr (biểu diễn heap), kích thước hiện tại n, và chỉ số i của nút cần xử lý.
- largest ban đầu được gán bằng i, giả định nút hiện tại là lớn nhất.
- Chỉ số của con trái (left_child) và con phải (right_child) được tính toán dựa trên công thức 2*i+1 và 2*i+2.
- Chúng ta kiểm tra xem con trái/phải có tồn tại (chỉ số nhỏ hơn n) và liệu giá trị của chúng có lớn hơn giá trị tại largest hiện tại hay không. Nếu có, cập nhật largest thành chỉ số của con đó.
- Sau khi kiểm tra cả hai con, largest sẽ chứa chỉ số của nút có giá trị lớn nhất trong ba (nút i, con trái, con phải).
- Nếu largest khác với i (tức là nút i không phải là lớn nhất), chúng ta hoán đổi giá trị tại i và largest bằng std::swap.
- Sau hoán đổi, phần tử ban đầu ở i đã di chuyển xuống vị trí largest. Để đảm bảo cây con tại largest vẫn là Heap hợp lệ, chúng ta gọi đệ quy hàm heapify trên chỉ số largest mới.
- Quá trình đệ quy dừng lại khi điều kiện largest != i không còn đúng, tức là nút hiện tại đã ở đúng vị trí của nó hoặc đã đi xuống đến mức lá.
- Độ phức tạp thời gian của heapify là O(log n), vì trong trường hợp xấu nhất, chúng ta đi xuống một đường từ gốc đến lá, và chiều cao của cây nhị phân đầy đủ là log n.

2. Thao tác `Insert` (hay `siftUp` / `bubbleUp`)

Khi thêm một phần tử mới vào Heap, chúng ta cần đảm bảo thuộc tính Heap vẫn được duy trì.

Mục đích: Thêm một phần tử mới vào Heap và điều chỉnh cấu trúc để nó vẫn là một Heap hợp lệ.
Cách hoạt động (với Max Heap):
1. Thêm phần tử mới vào vị trí cuối cùng của mảng (để giữ thuộc tính cây đầy đủ).
2. Bubble up (hoặc sift up) phần tử mới: So sánh nó với nút cha của nó.
3. Nếu phần tử mới lớn hơn nút cha (vi phạm Max Heap property), hoán đổi chúng.
4. Tiếp tục quá trình này lên phía trên cây cho đến khi phần tử mới không còn lớn hơn nút cha của nó, hoặc nó đã đi lên đến gốc.
Code minh họa insert trong C++ (cho Max Heap):

// Hàm thêm một phần tử vào Max Heap
void insert(std::vector<int>& arr, int value) {
    // Thêm phần tử mới vào cuối vector
    arr.push_back(value);

    // Lấy chỉ số của phần tử vừa thêm
    int current_index = arr.size() - 1;

    // Bubble up (sift up) phần tử mới
    // Vòng lặp chạy cho đến khi phần tử ở gốc (index > 0)
    // và giá trị của nó lớn hơn giá trị của cha (vi phạm Max Heap property)
    while (current_index > 0 && arr[current_index] > arr[(current_index - 1) / 2]) {
        // Tính chỉ số cha
        int parent_index = (current_index - 1) / 2;

        // Hoán đổi phần tử hiện tại với cha
        std::swap(arr[current_index], arr[parent_index]);

        // Di chuyển lên vị trí của cha để tiếp tục kiểm tra
        current_index = parent_index;
    }
}

// Example usage (trong hàm main hoặc riêng)
/*
int main() {
    std::vector<int> myHeap; // Bắt đầu với heap rỗng

    std::cout << "Inserting 10..." << std::endl;
    insert(myHeap, 10); // Heap: [10]
    printHeap(myHeap);

    std::cout << "Inserting 5..." << std::endl;
    insert(myHeap, 5);  // Heap: [10, 5]
    printHeap(myHeap);

    std::cout << "Inserting 15..." << std::endl;
    insert(myHeap, 15); // Heap: [10, 5, 15] -> sift up 15 -> [15, 5, 10]
    printHeap(myHeap);

    std::cout << "Inserting 2..." << std::endl;
    insert(myHeap, 2);  // Heap: [15, 5, 10, 2]
    printHeap(myHeap);

    std::cout << "Inserting 12..." << std::endl;
    insert(myHeap, 12); // Heap: [15, 5, 10, 2, 12] -> sift up 12 -> [15, 12, 10, 2, 5]
    printHeap(myHeap);

    return 0;
}
*/

Giải thích code insert:
- Hàm nhận vào vector arr và giá trị value cần thêm.
- value được thêm vào cuối vector bằng arr.push_back(). Điều này đảm bảo thuộc tính cây đầy đủ vẫn đúng.
- current_index được gán là chỉ số của phần tử mới thêm vào.
- Vòng lặp while thực hiện thao tác bubble up. Điều kiện lặp là:
  - current_index > 0: Đảm bảo chúng ta chưa đến gốc.
  - arr[current_index] > arr[(current_index - 1) / 2]: Kiểm tra xem giá trị hiện tại có lớn hơn giá trị của nút cha hay không (đang vi phạm Max Heap property).
- Bên trong vòng lặp:
  - Chỉ số của nút cha (parent_index) được tính.
  - Hoán đổi giá trị tại current_index và parent_index.
  - Cập nhật current_index thành parent_index để tiếp tục kiểm tra với nút cha mới (nút mà phần tử vừa được hoán đổi lên).
- Vòng lặp kết thúc khi phần tử mới tìm được vị trí đúng của nó (không còn lớn hơn cha) hoặc đã lên đến gốc.
- Độ phức tạp thời gian của insert là O(log n), vì trong trường hợp xấu nhất, phần tử mới sẽ đi từ lá lên đến gốc, và chiều cao của cây là log n.

3. Thao tác `extractMax` (cho Max Heap)

Thao tác này loại bỏ và trả về phần tử có độ ưu tiên cao nhất (phần tử lớn nhất trong Max Heap, nhỏ nhất trong Min Heap), tức là phần tử ở nút gốc.

Mục đích: Loại bỏ và trả về phần tử ở gốc của Heap.
Cách hoạt động (với Max Heap):
1. Kiểm tra Heap có rỗng không. Nếu rỗng, báo lỗi hoặc trả về giá trị đặc biệt.
2. Lưu lại giá trị của nút gốc (đây là phần tử lớn nhất cần trả về).
3. Để duy trì thuộc tính cây đầy đủ và chuẩn bị cho việc khôi phục thuộc tính Heap, chúng ta thay thế nút gốc bằng phần tử cuối cùng trong mảng.
4. Xóa phần tử cuối cùng khỏi mảng (giảm kích thước Heap đi 1).
5. Gọi hàm heapify (hoặc siftDown) trên nút gốc mới (chỉ số 0) để đưa nó về đúng vị trí và khôi phục thuộc tính Heap cho toàn bộ cây.
6. Trả về giá trị đã lưu ở bước 2.
Code minh họa extractMax trong C++ (cho Max Heap):

#include <stdexcept> // Để sử dụng std::runtime_error

// Hàm xóa và trả về phần tử lớn nhất từ Max Heap
int extractMax(std::vector<int>& arr) {
    // Kiểm tra heap rỗng
    if (arr.empty()) {
        throw std::runtime_error("Heap is empty!");
    }

    // Lưu giá trị gốc (phần tử lớn nhất)
    int root_value = arr[0];

    // Thay thế gốc bằng phần tử cuối cùng
    arr[0] = arr.back();

    // Xóa phần tử cuối cùng (giảm kích thước heap)
    arr.pop_back();

    // Gọi heapify từ gốc để khôi phục thuộc tính Max Heap
    // Kích thước mới của heap là arr.size()
    if (!arr.empty()) { // Chỉ heapify nếu heap không rỗng sau khi xóa
        heapify(arr, arr.size(), 0);
    }

    // Trả về giá trị đã lưu
    return root_value;
}

// Example usage (trong hàm main hoặc riêng)
/*
int main() {
    std::vector<int> myHeap = {15, 12, 10, 2, 5}; // Max Heap hợp lệ

    std::cout << "Heap before extractMax: ";
    printHeap(myHeap); // Output: 15 12 10 2 5

    try {
        int max_val = extractMax(myHeap);
        std::cout << "Extracted max value: " << max_val << std::endl; // Output: 15
        std::cout << "Heap after extractMax: ";
        printHeap(myHeap); // Output: 12 5 10 2 (hoặc 12 2 10 5 tùy cài đặt heapify) -> Đúng là 12 5 10 2

        max_val = extractMax(myHeap);
        std::cout << "Extracted max value: " << max_val << std::endl; // Output: 12
        std::cout << "Heap after extractMax: ";
        printHeap(myHeap); // Output: 10 2 5 (hoặc 10 5 2) -> Đúng là 10 2 5

    } catch (const std::runtime_error& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }

    return 0;
}
*/

Giải thích code extractMax:
- Hàm nhận vào vector arr (Heap).
- Kiểm tra arr.empty() để xử lý trường hợp Heap rỗng, ném ra ngoại lệ nếu cần.
- Lưu giá trị tại arr[0] (gốc) vào biến root_value.
- Gán giá trị của phần tử cuối cùng (arr.back()) cho arr[0].
- Sử dụng arr.pop_back() để loại bỏ phần tử cuối cùng, hiệu quả là giảm kích thước logic của Heap.
- Sau khi thay thế gốc, Heap có thể không còn thỏa mãn thuộc tính Max Heap. Chúng ta gọi heapify(arr, arr.size(), 0) để khôi phục thuộc tính này từ gốc (chỉ số 0) với kích thước mới của Heap.
- Cuối cùng, hàm trả về root_value đã lưu.
- Độ phức tạp thời gian của extractMax là O(log n), chủ yếu do thao tác heapify sau khi xóa gốc.

4. Thao tác `buildHeap` (Xây dựng Heap từ Mảng)

Thao tác này biến một mảng (hoặc vector) bất kỳ thành một Heap hợp lệ.

Mục đích: Chuyển đổi một mảng thành Max Heap (hoặc Min Heap).
Cách hoạt động (với Max Heap):
1. Chúng ta biết rằng các nút lá (leaf nodes) luôn là Heap hợp lệ theo định nghĩa (vì chúng không có con để vi phạm thuộc tính).
2. Thuộc tính cây nhị phân đầy đủ cho phép chúng ta xác định chỉ số của nút không phải lá cuối cùng trong mảng. Đối với mảng 0-based index có kích thước n, nút không phải lá cuối cùng nằm ở chỉ số (n / 2) - 1.
3. Chúng ta có thể xây dựng Heap bằng cách duyệt ngược từ nút không phải lá cuối cùng lên đến gốc (chỉ số 0), và gọi heapify cho từng nút đó.
4. Khi heapify được gọi tại một nút i, nó đảm bảo rằng cây con gốc i trở thành Heap hợp lệ, giả sử rằng các cây con của nó (mà chúng ta đã xử lý trước đó trong vòng lặp ngược) đã là Heap hợp lệ.
Code minh họa buildHeap trong C++ (cho Max Heap):

// Hàm xây dựng Max Heap từ một vector bất kỳ
void buildHeap(std::vector<int>& arr) {
    int n = arr.size();

    // Duyệt ngược từ nút không phải lá cuối cùng lên đến gốc
    // Chỉ số của nút không phải lá cuối cùng là (n/2) - 1 (với 0-based indexing)
    for (int i = n / 2 - 1; i >= 0; i--) {
        // Gọi heapify cho mỗi nút không phải lá
        heapify(arr, n, i);
    }
}

// Example usage (trong hàm main hoặc riêng)
/*
int main() {
    std::vector<int> initial_arr = {4, 10, 3, 5, 1, 2};

    std::cout << "Initial array: ";
    printHeap(initial_arr); // Output: 4 10 3 5 1 2

    buildHeap(initial_arr);

    std::cout << "Max Heap after buildHeap: ";
    printHeap(initial_arr); // Output: 10 5 3 4 1 2 (hoặc một permutation hợp lệ khác) -> Output: 10 5 3 4 1 2 là đúng

    // Kiểm tra thuộc tính Heap:
    // Gốc 10 > 5 và 3
    // 5 > 4 và 1
    // 3 > 2
    // Các lá 4, 1, 2 là heap 1 nút
    // -> Đã là Max Heap hợp lệ

    return 0;
}
*/

Giải thích code buildHeap:
- Hàm nhận vào vector arr cần chuyển đổi.
- n là kích thước của vector.
- Vòng lặp for bắt đầu từ chỉ số (n / 2) - 1 (nút không phải lá cuối cùng) và đi ngược về 0 (gốc).
- Trong mỗi lần lặp, chúng ta gọi heapify trên nút tại chỉ số i. Hàm heapify này sẽ "đẩy" phần tử tại i xuống đúng vị trí của nó trong cây con, đảm bảo cây con đó trở thành một Heap hợp lệ. Vì chúng ta duyệt ngược từ dưới lên, khi xử lý một nút i, các cây con của nó (con trái ở 2*i+1, con phải ở 2*i+2) đã được xử lý và là Heap hợp lệ (hoặc là nút lá).
- Sau khi vòng lặp kết thúc tại chỉ số 0, toàn bộ cây sẽ là một Heap hợp lệ.
- Độ phức tạp thời gian của buildHeap là một kết quả ngạc nhiên nhưng quan trọng: O(n). Mặc dù heapify tốn O(log n), không phải tất cả các nút đều ở mức cao nhất. Tổng thời gian thực hiện heapify trên tất cả các nút từ dưới lên hóa ra là tuyến tính theo số lượng phần tử.

Ứng dụng của Heap: Priority Queue

Ứng dụng phổ biến nhất và cũng là minh chứng rõ ràng nhất cho sức mạnh của Heap chính là việc triển khai Priority Queue (Hàng đợi ưu tiên).

Một Hàng đợi ưu tiên là một cấu trúc dữ liệu trừu tượng giống như hàng đợi thông thường, nhưng thay vì tuân theo nguyên tắc FIFO (First-In, First-Out), nó tuân theo nguyên tắc ưu tiên. Khi lấy phần tử ra khỏi hàng đợi, chúng ta luôn lấy phần tử có độ ưu tiên cao nhất (hoặc thấp nhất, tùy thuộc vào định nghĩa).

Nếu sử dụng Max Heap, chúng ta có Hàng đợi ưu tiên mà phần tử có giá trị lớn nhất có độ ưu tiên cao nhất.
Nếu sử dụng Min Heap, chúng ta có Hàng đợi ưu tiên mà phần tử có giá trị nhỏ nhất có độ ưu tiên cao nhất.

Các thao tác chính của Hàng đợi ưu tiên:

Insert (Thêm): Thêm một phần tử mới vào hàng đợi. Với Heap, thao tác này tương ứng với việc thêm vào Heap và thực hiện sift up. Độ phức tạp O(log n).
Extract (Lấy ra phần tử ưu tiên nhất): Loại bỏ và trả về phần tử có độ ưu tiên cao nhất. Với Heap, thao tác này tương ứng với việc extractMax (hoặc extractMin). Độ phức tạp O(log n).
Peek/Top (Xem phần tử ưu tiên nhất): Chỉ xem giá trị của phần tử ưu tiên nhất mà không xóa nó. Với Heap, thao tác này chỉ đơn giản là trả về giá trị tại chỉ số 0 (gốc). Độ phức tạp O(1).

Heap là lựa chọn tối ưu cho Priority Queue vì nó cung cấp hiệu suất O(log n) cho các thao tác thêm và xóa, nhanh hơn nhiều so với O(n) nếu sử dụng mảng/vector thông thường, và đơn giản hơn so với cây tìm kiếm nhị phân cân bằng (Balanced BST) trong việc chỉ cần truy cập phần tử lớn nhất/nhỏ nhất.

Trong C++, thư viện chuẩn cung cấp std::priority_queue được cài đặt sẵn dựa trên Heap, cho phép bạn sử dụng Hàng đợi ưu tiên một cách dễ dàng.

Độ phức tạp của các Thao tác trên Heap

Tổng kết độ phức tạp thời gian của các thao tác chính trên một Binary Heap (kích thước n):

heapify (siftDown): O(log n)
insert (siftUp): O(log n)
extractMax/extractMin: O(log n)
buildHeap (từ mảng): O(n)
peek/top (xem gốc): O(1)

Độ phức tạp không gian: O(n) để lưu trữ các phần tử trong mảng.

Tại sao Heap lại hiệu quả?

Sự hiệu quả của Heap đến từ hai yếu tố chính:

Biểu diễn mảng: Giúp truy cập các phần tử cha/con một cách nhanh chóng O(1) mà không cần đi theo con trỏ.
Thuộc tính Heap: Đảm bảo rằng phần tử ưu tiên nhất luôn ở gốc, cho phép truy cập O(1). Các thao tác thêm/xóa chỉ yêu cầu di chuyển (sift/bubble) một phần tử dọc theo một đường từ gốc đến lá hoặc ngược lại. Chiều dài của đường này là chiều cao của cây, chỉ O(log n) cho một cây nhị phân đầy đủ.

Bài tập ví dụ:

Trò chơi Trung vị

Trong một buổi thảo luận về vật lý lượng tử, FullHouse Dev đã được đưa ra một bài toán thú vị liên quan đến trung vị của dãy số. Mặc dù không trực tiếp liên quan đến vật lý, nhưng bài toán này đã kích thích trí tò mò của nhóm và họ quyết định giải quyết nó.

Bài toán

Bạn được cho một mảng \(A\) gồm \(N\) số nguyên. Bạn thực hiện thao tác sau \(N\) lần: Với mỗi mảng con liên tiếp có kích thước lẻ lớn hơn \(1\), bạn tìm trung vị của mỗi mảng con (Giả sử các trung vị thu được trong một lượt là \(M_1, M_2, ...\)). Trong mỗi lượt, bạn loại bỏ phần tử đầu tiên có giá trị \(min(M_1, M_2, ...)\) khỏi mảng ban đầu. Sau khi loại bỏ phần tử, kích thước mảng giảm đi 1 và không có khoảng trống nào được để lại.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(T\) là số lượng bộ test (\(1 \leq T \leq 10\)).
Dòng đầu tiên của mỗi bộ test chứa số nguyên \(N\) là số lượng phần tử trong mảng ban đầu (\(1 \leq N \leq 10^5\)).
Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn mảng \(A\) (\(1 \leq A_i \leq 10^9\) với mọi \(i\) hợp lệ).

OUTPUT FORMAT:

Với mỗi bộ test, in ra một số nguyên duy nhất biểu diễn tổng các số còn lại trong mảng sau khi thực hiện các thao tác.

VÍ DỤ:

INPUT

OUTPUT

7
2

Giải thích:

Đối với bộ test đầu tiên: Ban đầu, mảng là \([2, 5, 3, 2]\). Các trung vị thu được là \(2\) và \(3\) cho các mảng con \([2, 5, 3]\) và \([5, 3, 2]\) tương ứng. Do đó, chúng ta loại bỏ \(2\) khỏi mảng ban đầu. Mảng bây giờ trở thành \([5, 3, 2]\). Trung vị của toàn bộ mảng là \(3\). Do đó, chúng ta loại bỏ lần xuất hiện đầu tiên của \(3\) khỏi mảng. Vậy chúng ta còn lại với mảng \([5, 2]\).
Đối với bộ test thứ hai, rõ ràng trung vị nhỏ nhất sẽ luôn là \(1\) mỗi lần. Do đó, cuối cùng chúng ta sẽ còn lại với mảng \([1, 1]\). Đây là hướng dẫn giải bài "Trò chơi Trung vị" một cách ngắn gọn, tập trung vào ý tưởng và cấu trúc thuật toán, có xem xét đến hiệu quả:

Hiểu rõ thao tác:
- Bài toán yêu cầu lặp đi lặp lại một thao tác loại bỏ phần tử.
- Thao tác này dựa trên việc tìm trung vị của tất cả các mảng con liên tiếp có kích thước lẻ và lớn hơn 1 (tức là kích thước 3, 5, 7,...).
- Tìm giá trị nhỏ nhất m trong tập hợp các trung vị này.
- Loại bỏ phần tử đầu tiên có giá trị m khỏi mảng hiện tại.
- Mảng co lại sau khi loại bỏ.
- Thao tác được lặp lại N lần (hoặc cho đến khi mảng không còn mảng con lẻ > 1, tức là kích thước mảng nhỏ hơn 3). Dựa vào ví dụ, có vẻ quá trình dừng khi kích thước mảng nhỏ hơn 3.
Phân tích Ví dụ và Giả định:
- Ví dụ 1 ([2, 5, 3, 2]): Mảng con size 3 là [2, 5, 3] và [5, 3, 2].
  - Trung vị chuẩn của [2, 5, 3] là 3 (sau khi sắp xếp [2, 3, 5]).
  - Trung vị chuẩn của [5, 3, 2] là 3 (sau khi sắp xếp [2, 3, 5]).
  - Tập trung vị là {3}. Giá trị nhỏ nhất là 3. Loại bỏ 3 đầu tiên -> [2, 5, 2].
  - Tiếp theo: [2, 5, 2]. Mảng con size 3 là [2, 5, 2]. Trung vị chuẩn là 2 (sau sắp xếp [2, 2, 5]). Giá trị nhỏ nhất là 2. Loại bỏ 2 đầu tiên -> [5, 2].
  - Kích thước mảng là 2 (<3), dừng. Tổng còn lại: 5 + 2 = 7.
- Ví dụ 2 ([1, 1, 1, 1]):
  - Mảng con size 3: [1, 1, 1], [1, 1, 1]. Trung vị 1, 1. Min 1. Loại bỏ 1 đầu tiên -> [1, 1, 1].
  - Mảng con size 3: [1, 1, 1]. Trung vị 1. Min 1. Loại bỏ 1 đầu tiên -> [1, 1].
  - Kích thước 2 (<3), dừng. Tổng còn lại: 1 + 1 = 2.
- Quan sát từ ví dụ: Quá trình dừng khi kích thước mảng < 3. Trung vị được tính theo nghĩa chuẩn (element ở giữa sau khi sắp xếp). Có vẻ như chỉ cần xét trung vị của mảng con kích thước 3 là đủ để tìm ra giá trị nhỏ nhất trong tập hợp tất cả các trung vị (đây là giả định để giảm độ phức tạp, vì việc tính trung vị cho mảng con lớn hơn rất tốn kém).
Cấu trúc dữ liệu:
- Mảng thay đổi kích thước và cần xóa phần tử ở vị trí bất kỳ (hoặc theo giá trị).
- Cần lặp qua các phần tử để xác định mảng con liên tiếp và tìm phần tử đầu tiên có giá trị cần xóa.
- std::vector trong C++: Xóa phần tử mất O(k) (k là số phần tử sau vị trí xóa). Tổng cộng O(N^2) cho N bước xóa.
- std::list trong C++: Xóa phần tử mất O(1) nếu có iterator. Tuy nhiên, tìm iterator đến phần tử đầu tiên có giá trị cần xóa mất O(N). Lặp qua list để tìm mảng con liên tiếp cũng mất O(N). Tổng cộng O(N) mỗi bước, N bước là O(N^2).
- Với N lên tới 10^5, O(N^2) là quá chậm (10^10 phép tính). Tuy nhiên, nếu giả định rằng chỉ cần xét mảng con size 3, và sử dụng std::list, ta có thể cài đặt mô phỏng O(N^2). Với ràng buộc T=10, có thể tổng N qua các testcase không quá lớn, hoặc testcase không chạm đến trường hợp xấu nhất của O(N^2), hoặc đây là bài có mẹo/cấu trúc dữ liệu nâng cao mà O(N^2) là cách mô phỏng cơ bản. Dựa vào mức độ phổ biến trong các bài tập, O(N^2) mô phỏng với std::list (kết hợp giả định size 3) là hướng đi khả dĩ nhất dựa trên mô tả và ví dụ.
Thuật toán (Mô phỏng dùng std::list):
- Đọc N và mảng A vào một std::list<int> current_array.
- Nếu N < 3, tính tổng và in ra luôn.
- Lặp N-2 lần (vì mỗi lần loại bỏ 1 phần tử, cần N-2 lần loại bỏ để kích thước từ N về 2):
  - Khởi tạo min_median = infinity, value_to_remove = infinity.
  - Duyệt list current_array với 3 iterator trỏ đến 3 phần tử liên tiếp (a, b, c).
  - Tính trung vị m = median(a, b, c) (sắp xếp 3 giá trị và lấy giá trị ở giữa).
  - Nếu m < min_median, cập nhật min_median = m.
  - Lưu ý: Cần tìm giá trị min_median nhỏ nhất trong tất cả các mảng con size 3.
  - Sau khi tìm được giá trị min_median nhỏ nhất trong lượt này:
    - Duyệt list current_array từ đầu để tìm phần tử đầu tiên có giá trị bằng min_median.
    - Xóa phần tử đó khỏi list bằng iterator tương ứng.
- Sau khi vòng lặp kết thúc (kích thước list <= 2), tính tổng các phần tử còn lại trong list và in ra.
Cách tính median(a, b, c):
- Có thể dùng min({a, b, c}) và max({a, b, c}). Trung vị là a + b + c - min({a, b, c}) - max({a, b, c}).
Tối ưu (nếu O(N^2) quá chậm):
- Việc tìm min(median(a, b, c)) cho tất cả bộ 3 liên tiếp mất O(K) với K là kích thước hiện tại của list. Nếu có cấu trúc dữ liệu giúp tìm minimum trên "cửa sổ trượt" của hàm median(a, b, c) một cách hiệu quả hơn, hoặc một quan sát toán học về các phần tử bị xóa, thì có thể đạt O(N log N) hoặc O(N). Tuy nhiên, cách mô phỏng trực tiếp như trên là phương án dễ nghĩ ra nhất dựa trên mô tả bài toán.

Kết luận hướng giải: Sử dụng std::list để mô phỏng trực tiếp quá trình. Lặp lại N-2 lần (cho N>=3, với N<3 không loại bỏ). Trong mỗi bước lặp:

Duyệt std::list để tìm tất cả bộ 3 phần tử liên tiếp (a, b, c).
Tính trung vị chuẩn median(a, b, c) cho mỗi bộ.
Tìm giá trị nhỏ nhất m trong tập hợp các trung vị vừa tính.
Duyệt std::list từ đầu để tìm phần tử đầu tiên có giá trị m.
Xóa phần tử đó khỏi list. Sau N-2 bước (hoặc khi list còn < 3 phần tử), tính tổng các phần tử còn lại trong list.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.