Bài 15.5. Bài tập tổng hợp về Merge và Heap Sort

Chào mừng trở lại với series Cấu trúc dữ liệu và Giải thuật!

Sau khi đã đi sâu vào lý thuyết và cách hoạt động của Merge Sort và Heap Sort - hai trong số những giải thuật sắp xếp mạnh mẽ và hiệu quả nhất, đã đến lúc chúng ta thử sức với các bài tập thực tế. Lý thuyết là nền tảng, nhưng việc áp dụng chúng vào các tình huống cụ thể mới thực sự giúp chúng ta nắm vững và hiểu sâu sắc sức mạnh cũng như hạn chế của từng giải thuật.

Bài viết này sẽ tổng hợp một số bài tập tiêu biểu, đòi hỏi bạn phải vận dụng linh hoạt kiến thức về Merge Sort và Heap Sort, không chỉ đơn thuần là code lại giải thuật sắp xếp. Chúng ta sẽ cùng nhau phân tích vấn đề, tìm ra cách giải quyết hiệu quả nhất dựa trên cấu trúc và ý tưởng cốt lõi của hai giải thuật này, và triển khai bằng C++.

Hãy sẵn sàng để thử thách bản thân!

Nhắc lại ngắn gọn về Merge Sort và Heap Sort

Trước khi đi vào bài tập, hãy cùng điểm lại ngắn gọn về hai giải thuật này để làm nóng kiến thức:

Merge Sort:
- Ý tưởng chính: Chia để trị (Divide and Conquer). Chia mảng thành hai nửa, đệ quy sắp xếp từng nửa, sau đó hợp nhất (merge) hai nửa đã sắp xếp.
- Đặc điểm: Ổn định (stable sort). Hiệu quả ngay cả với danh sách liên kết.
- Độ phức tạp thời gian: O(n log n) trong mọi trường hợp (best, average, worst).
- Độ phức tạp không gian: O(n) cho mảng tạm khi hợp nhất.
Heap Sort:
- Ý tưởng chính: Dựa trên cấu trúc dữ liệu Heap (thường là Max-Heap). Xây dựng một Max-Heap từ mảng, phần tử lớn nhất nằm ở gốc. Lặp lại quá trình đưa phần tử gốc ra cuối mảng và vun đống lại phần còn lại.
- Đặc điểm: Sắp xếp tại chỗ (in-place sort) với O(1) không gian phụ nếu không tính không gian đầu vào. Không ổn định (not stable).
- Độ phức tạp thời gian: O(n log n) trong mọi trường hợp.
- Độ phức tạp không gian: O(1) (nếu thực hiện tại chỗ).

Giờ thì, hãy bắt tay vào giải quyết các bài tập!

Bài tập 1: Đếm cặp nghịch thế (Counting Inversions)

Phát biểu bài toán: Cho một mảng các số nguyên arr. Một cặp chỉ số (i, j) được gọi là một cặp nghịch thế nếu i < j và arr[i] > arr[j]. Nhiệm vụ của bạn là đếm tổng số cặp nghịch thế trong mảng đã cho.

Ví dụ:

arr = [2, 4, 1, 3, 5]
- Các cặp nghịch thế là: (2, 1), (4, 1), (4, 3).
- Tổng số cặp nghịch thế là 3.
arr = [5, 4, 3, 2, 1]
- Các cặp nghịch thế là: (5, 4), (5, 3), (5, 2), (5, 1), (4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1).
- Tổng số cặp nghịch thế là 10.

Phân tích và Lựa chọn Giải Thuật:

Nếu bạn cố gắng đếm cặp nghịch thế bằng cách duyệt tất cả các cặp (i, j) với i < j và kiểm tra điều kiện arr[i] > arr[j], độ phức tạp sẽ là O(n²), không hiệu quả với mảng lớn.

Tuy nhiên, bài toán đếm cặp nghịch thế có một mối liên hệ sâu sắc với Merge Sort. Hãy nhớ lại quá trình hợp nhất trong Merge Sort: chúng ta hợp nhất hai mảng con đã được sắp xếp. Khi ta lấy một phần tử từ mảng con phải và đưa nó vào mảng kết quả, nếu phần tử đó nhỏ hơn phần tử hiện tại ở mảng con trái, điều đó có nghĩa là phần tử từ mảng con phải này tạo thành một cặp nghịch thế với phần tử hiện tại ở mảng con trái và tất cả các phần tử còn lại trong mảng con trái đó (vì mảng con trái đã được sắp xếp).

Đây chính là điểm mấu chốt! Chúng ta có thể kết hợp quá trình đếm nghịch thế vào chính giải thuật Merge Sort mà không làm tăng đáng kể độ phức tạp thời gian.

Cách tiếp cận:

Giải thuật đếm nghịch thế dựa trên Merge Sort sẽ có cấu trúc tương tự.
Hàm đệ quy sẽ chia mảng thành hai nửa, đệ quy gọi chính nó để đếm nghịch thế trong từng nửa.
Quan trọng nhất, hàm hợp nhất (merge) sẽ được sửa đổi để không chỉ hợp nhất hai nửa đã sắp xếp mà còn đếm số cặp nghịch thế được tạo ra giữa hai nửa đó trong quá trình hợp nhất.
Tổng số nghịch thế sẽ là tổng của nghịch thế trong nửa trái, nghịch thế trong nửa phải, và nghịch thế giữa hai nửa.

Triển khai bằng C++:

Chúng ta cần một hàm mergeAndCount để hợp nhất và đếm, và một hàm mergeSortAndCount để thực hiện đệ quy.

#include <iostream>
#include <vector>
#include <algorithm> // for std::copy

using namespace std;

// Hàm hợp nhất hai mảng con đã sắp xếp và đếm nghịch thế giữa chúng
long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    long long inversionCount = 0;

    // Kích thước và tạo mảng tạm cho nửa trái và nửa phải
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> leftArray(n1);
    vector<int> rightArray(n2);

    // Sao chép dữ liệu vào mảng tạm
    for (int i = 0; i < n1; i++)
        leftArray[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArray[j] = arr[mid + 1 + j];

    // Hợp nhất mảng tạm trở lại arr[left..right]
    int i = 0; // Chỉ số bắt đầu của leftArray
    int j = 0; // Chỉ số bắt đầu của rightArray
    int k = left; // Chỉ số bắt đầu của mảng gốc (để ghi kết quả hợp nhất)

    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            // Phần tử từ nửa trái nhỏ hơn hoặc bằng nửa phải
            // Không có nghịch thế nào được tạo ra với phần tử rightArray[j]
            arr[k] = leftArray[i];
            i++;
        } else {
            // Phần tử từ nửa phải nhỏ hơn phần tử từ nửa trái
            // Điều này tạo ra nghịch thế với phần tử leftArray[i]
            // VÀ TẤT CẢ các phần tử còn lại trong leftArray (vì leftArray đã được sắp xếp)
            arr[k] = rightArray[j];
            j++;
            // Số nghịch thế được tạo ra bằng số phần tử còn lại trong leftArray từ vị trí i
            inversionCount += (long long)(n1 - i);
        }
        k++;
    }

    // Sao chép các phần tử còn lại của leftArray (nếu có)
    while (i < n1) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }

    // Sao chép các phần tử còn lại của rightArray (nếu có)
    while (j < n2) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }

    return inversionCount;
}

// Hàm đệ quy thực hiện Merge Sort và đếm tổng nghịch thế
long long mergeSortAndCount(vector<int>& arr, int left, int right) {
    long long totalInversions = 0;
    if (left < right) {
        int mid = left + (right - left) / 2; // Tránh tràn số với (left + right) / 2

        // Đếm nghịch thế trong nửa trái (đệ quy)
        totalInversions += mergeSortAndCount(arr, left, mid);

        // Đếm nghịch thế trong nửa phải (đệ quy)
        totalInversions += mergeSortAndCount(arr, mid + 1, right);

        // Đếm nghịch thế giữa hai nửa và hợp nhất
        totalInversions += mergeAndCount(arr, left, mid, right);
    }
    return totalInversions;
}

int main() {
    vector<int> arr1 = {2, 4, 1, 3, 5};
    long long inversions1 = mergeSortAndCount(arr1, 0, arr1.size() - 1);
    cout << "Mang 1: [2, 4, 1, 3, 5]" << endl;
    cout << "So cap nghich the: " << inversions1 << endl; // Output: 3

    vector<int> arr2 = {5, 4, 3, 2, 1};
    long long inversions2 = mergeSortAndCount(arr2, 0, arr2.size() - 1);
    cout << "\nMang 2: [5, 4, 3, 2, 1]" << endl;
    cout << "So cap nghich the: " << inversions2 << endl; // Output: 10

    vector<int> arr3 = {1, 2, 3, 4, 5};
    long long inversions3 = mergeSortAndCount(arr3, 0, arr3.size() - 1);
    cout << "\nMang 3: [1, 2, 3, 4, 5]" << endl;
    cout << "So cap nghich the: " << inversions3 << endl; // Output: 0

    return 0;
}

Giải thích code:

Hàm mergeSortAndCount(arr, left, right): Đây là hàm đệ quy chính. Nó chia mảng arr từ left đến right thành hai nửa tại mid. Nó đệ quy gọi chính nó cho nửa trái (left đến mid) và nửa phải (mid + 1 đến right) để đếm nghịch thế bên trong từng nửa. Sau đó, nó gọi mergeAndCount để đếm nghịch thế giữa hai nửa và hợp nhất chúng. Tổng số nghịch thế là tổng của ba giá trị này.
Hàm mergeAndCount(arr, left, mid, right): Hàm này thực hiện việc hợp nhất tương tự như Merge Sort thông thường. Tuy nhiên, khi lấy một phần tử từ rightArray (rightArray[j]) và thấy rằng nó nhỏ hơn phần tử hiện tại của leftArray (leftArray[i]), chúng ta biết rằng rightArray[j] tạo thành một cặp nghịch thế với leftArray[i] và tất cả các phần tử còn lại trong leftArray bắt đầu từ vị trí i. Số lượng các phần tử này là (n1 - i). Chúng ta cộng giá trị này vào inversionCount. Sau khi vòng lặp hợp nhất kết thúc, inversionCount chứa tổng số nghịch thế được tạo ra giữa hai nửa leftArray và rightArray.
Mảng arr được truyền bằng tham chiếu (vector<int>& arr) để hàm mergeAndCount có thể sắp xếp tại chỗ trong phạm vi [left, right] của mảng gốc sau khi đếm. Điều này đảm bảo mảng con được sắp xếp trước khi quay lại cấp đệ quy cao hơn.
Sử dụng long long cho inversionCount là quan trọng vì số lượng nghịch thế có thể rất lớn (lên tới n*(n-1)/2).
Việc tính mid = left + (right - left) / 2 thay vì (left + right) / 2 giúp tránh tràn số khi left và right là các số nguyên lớn.

Độ phức tạp của giải thuật này vẫn là O(n log n) thời gian và O(n) không gian, giống như Merge Sort gốc, vì công việc đếm nghịch thế trong hàm mergeAndCount chỉ thêm một vòng lặp tuyến tính O(n) vào quá trình hợp nhất vốn dĩ đã là O(n).

Bài tập 2: Tìm phần tử lớn thứ k (Find k-th Largest Element)

Phát biểu bài toán: Cho một mảng các số nguyên không sắp xếp arr và một số nguyên k. Tìm phần tử lớn thứ k trong mảng. Lưu ý: Đây là phần tử lớn thứ k nếu mảng được sắp xếp, không phải là phần tử phân biệt thứ k.

Ví dụ:

arr = [3, 2, 1, 5, 6, 4], k = 2
- Mảng đã sắp xếp: [1, 2, 3, 4, 5, 6]
- Phần tử lớn thứ 2 là 5.
arr = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
- Mảng đã sắp xếp: [1, 2, 2, 3, 3, 4, 5, 5, 6]
- Phần tử lớn thứ 4 là 4.

Phân tích và Lựa chọn Giải Thuật:

Cách đơn giản nhất để giải bài toán này là sắp xếp toàn bộ mảng (ví dụ dùng Merge Sort hoặc Heap Sort) và sau đó lấy phần tử ở vị trí n - k (hoặc k - 1 tùy cách đếm từ đầu hay cuối). Tuy nhiên, việc sắp xếp toàn bộ mảng mất O(n log n) thời gian. Chúng ta có thể làm tốt hơn.

Đây là nơi cấu trúc dữ liệu Heap phát huy sức mạnh, đặc biệt là std::priority_queue trong C++. Chúng ta không cần sắp xếp toàn bộ mảng, chỉ cần duy trì một tập hợp các phần tử "ứng cử viên" cho vị trí thứ k.

Cách tiếp cận sử dụng Heap (Min-Heap):

Sử dụng một Min-Heap (ưu tiên phần tử nhỏ nhất) để lưu trữ k phần tử lớn nhất mà chúng ta đã thấy cho đến nay.
Duyệt qua từng phần tử trong mảng arr.
Với mỗi phần tử, thêm nó vào Min-Heap.
Nếu kích thước của Min-Heap vượt quá k, hãy loại bỏ phần tử nhỏ nhất khỏi heap (phần tử ở gốc) bằng cách gọi pop(). Thao tác này đảm bảo heap luôn chỉ chứa tối đa k phần tử lớn nhất trong số các phần tử đã được xử lý.
Sau khi duyệt qua toàn bộ mảng, phần tử nhỏ nhất trong Min-Heap (phần tử ở gốc) chính là phần tử lớn thứ k của toàn bộ mảng.

Tại sao lại dùng Min-Heap để tìm phần tử lớn thứ k? Bởi vì Min-Heap có kích thước k sẽ tự động giữ lại k phần tử lớn nhất. Khi gặp một phần tử mới, nếu nó lớn hơn phần tử nhỏ nhất trong heap (là phần tử nhỏ nhất trong tập hợp k phần tử lớn nhất hiện tại), ta loại bỏ phần tử nhỏ nhất đó và thêm phần tử mới vào. Như vậy, heap luôn cập nhật để chứa k phần tử lớn nhất. Sau khi duyệt xong, phần tử nhỏ nhất trong heap chính là phần tử lớn thứ k trong toàn bộ mảng.

Triển khai bằng C++:

Chúng ta sẽ sử dụng std::priority_queue với tùy chỉnh để hoạt động như một Min-Heap.

#include <iostream>
#include <vector>
#include <queue> // for std::priority_queue
#include <functional> // for std::greater

using namespace std;

// Hàm tìm phần tử lớn thứ k bằng Min-Heap
int findKthLargest(vector<int>& nums, int k) {
    // Tạo một Min-Heap
    // priority_queue<type, container, comparator>
    // std::greater<int> biến Max-Heap mặc định thành Min-Heap
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Duyệt qua tất cả các phần tử trong mảng
    for (int num : nums) {
        // Thêm phần tử vào heap
        minHeap.push(num);

        // Nếu kích thước heap vượt quá k, loại bỏ phần tử nhỏ nhất
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }

    // Sau khi duyệt xong, phần tử ở gốc Min-Heap chính là phần tử lớn thứ k
    return minHeap.top();
}

int main() {
    vector<int> arr1 = {3, 2, 1, 5, 6, 4};
    int k1 = 2;
    cout << "Mang 1: [3, 2, 1, 5, 6, 4], k = " << k1 << endl;
    cout << "Phan tu lon thu " << k1 << " la: " << findKthLargest(arr1, k1) << endl; // Output: 5

    vector<int> arr2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
    int k2 = 4;
    cout << "\nMang 2: [3, 2, 3, 1, 2, 4, 5, 5, 6], k = " << k2 << endl;
    cout << "Phan tu lon thu " << k2 << " la: " << findKthLargest(arr2, k2) << endl; // Output: 4

    return 0;
}

Giải thích code:

Chúng ta sử dụng std::priority_queue<int, vector<int>, greater<int>> để khai báo một Min-Heap.
- int: Kiểu dữ liệu của các phần tử.
- vector<int>: Container cơ bản dùng để lưu trữ các phần tử (heap được xây dựng trên vector).
- greater<int>: Comparator. Mặc định priority_queue là Max-Heap (sử dụng std::less), std::greater đảo ngược thứ tự, biến nó thành Min-Heap.
Duyệt qua từng num trong mảng nums.
minHeap.push(num): Thêm phần tử hiện tại vào heap. Thao tác này mất O(log H) thời gian, trong đó H là kích thước hiện tại của heap.
if (minHeap.size() > k) { minHeap.pop(); }: Nếu kích thước heap vượt quá k, chúng ta loại bỏ phần tử nhỏ nhất (phần tử ở gốc) bằng pop(). Thao tác này cũng mất O(log H) thời gian. Bằng cách này, chúng ta đảm bảo heap luôn chứa không quá k phần tử.
Sau vòng lặp, heap chứa k phần tử lớn nhất từ mảng ban đầu. Phần tử nhỏ nhất trong tập hợp này chính là phần tử lớn thứ k của toàn bộ mảng, và nó nằm ở gốc heap, truy cập bằng minHeap.top().

Độ phức tạp:

Thời gian: Chúng ta duyệt qua n phần tử của mảng. Với mỗi phần tử, chúng ta thực hiện thao tác push hoặc push và pop trên một heap có kích thước tối đa là k. Mỗi thao tác này mất O(log k) thời gian. Do đó, tổng độ phức tạp thời gian là O(n log k). Nếu k nhỏ hơn nhiều so với n, đây sẽ hiệu quả hơn O(n log n) của việc sắp xếp toàn bộ mảng.
Không gian: Chúng ta sử dụng một heap có kích thước tối đa là k. Do đó, độ phức tạp không gian là O(k).

Bài tập ví dụ:

Vị trí ngồi tối ưu

Trong một buổi thảo luận về thiết kế rạp chiếu phim, FullHouse Dev và các kiến trúc sư đã đưa ra một bài toán thú vị. Họ muốn tối ưu hóa trải nghiệm xem phim cho khách hàng dựa trên chiều cao. Với sự sáng tạo và tinh thần đồng đội, họ bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

Sam, một thành viên của FullHouse Dev, muốn đi xem phim cùng bạn bè tại Rạp chiếu phim Armstord. Rạp này có quy định đặc biệt: khách hàng sẽ được sắp xếp chỗ ngồi theo chiều cao. Sam, với tư cách là người tổ chức, muốn ngồi ở giữa để có góc nhìn tốt nhất. Ban đầu, Sam có $N$ người bạn (bao gồm cả Sam). Chiều cao của Sam và các bạn được cho trước.

Sam có thể thực hiện hai thao tác:

Mời thêm một người bạn mới có chiều cao $X$.
Hủy lời mời của bất kỳ người bạn nào.

Mỗi thao tác tốn một đơn vị thời gian. Sam muốn hoàn thành việc sắp xếp càng nhanh càng tốt.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên $T$ - số lượng test case.
Mỗi test case gồm hai dòng:
- Dòng đầu chứa hai số nguyên $N$ và $H$, trong đó $N$ là tổng số bạn của Sam và $H$ là chiều cao của Sam.
- Dòng thứ hai chứa $N$ số nguyên biểu thị chiều cao của bạn Sam.

OUTPUT FORMAT:

Với mỗi test case, in ra số lượng thao tác tối thiểu Sam cần thực hiện.

Ràng buộc:

$1 \leq T \leq 100$
$1 \leq N \leq 10^5$
$1 \leq H, \text{chiều cao bạn bè} \leq 10^9$

Lưu ý:

Sam luôn phải ngồi ở giữa và có số người ngồi bên trái và bên phải bằng nhau.
Chiều cao của Sam luôn là duy nhất.

Ví dụ

INPUT

OUTPUT

1
1

Giải thích

Ở test case đầu tiên: Sam có thể hủy lời mời của người bạn có chiều cao 4 (Chi phí = 1)
Ở test case thứ hai: Sam có thể mời thêm một người bạn có chiều cao 4 (Chi phí = 1) Tuyệt vời, đây là hướng dẫn giải bài "Vị trí ngồi tối ưu" bằng C++ một cách ngắn gọn, tập trung vào logic mà không cung cấp code hoàn chỉnh:

Phân tích bài toán:

Mục tiêu: Sam muốn ngồi ở giữa khi tất cả mọi người (Sam + bạn bè) được sắp xếp theo chiều cao.
Điều kiện "ở giữa": Số người thấp hơn Sam phải bằng số người cao hơn Sam. Điều này chỉ xảy ra khi tổng số người là một số lẻ, và Sam là người duy nhất có chiều cao H (đã được đảm bảo trong ràng buộc).
Các thao tác: Thêm bạn (cost 1), bớt bạn (cost 1). Mục tiêu là giảm thiểu tổng cost.
Input: N bạn ban đầu (không bao gồm Sam), chiều cao H của Sam, danh sách chiều cao của N bạn.

Hướng tiếp cận:

Xử lý chiều cao bằng H: Theo ràng buộc, chiều cao của Sam là duy nhất trong danh sách cuối cùng. Bất kỳ người bạn nào có chiều cao bằng H ban đầu đều phải bị loại bỏ. Đây là những thao tác bắt buộc.
Đếm số người thấp/cao hơn Sam: Duyệt qua danh sách N bạn ban đầu. Đếm số bạn có chiều cao < H (gọi là num_shorter) và số bạn có chiều cao > H (gọi là num_taller).
Cân bằng: Sau khi loại bỏ những người có chiều cao bằng H, chúng ta còn lại num_shorter người thấp hơn Sam và num_taller người cao hơn Sam. Để Sam ngồi ở giữa, số người thấp hơn phải bằng số người cao hơn.
Thao tác tối thiểu để cân bằng:
- Nếu num_shorter == num_taller, đã cân bằng, không cần thêm thao tác nào cho phần này.
- Nếu num_shorter != num_taller, ta cần thực hiện thao tác để làm cho hai số này bằng nhau. Số thao tác tối thiểu để làm cho hai số a và b bằng nhau là abs(a - b) (bằng cách loại bỏ số lượng chênh lệch từ phía có nhiều hơn, hoặc thêm vào phía có ít hơn). Trong bài toán này, để đạt được số lượng thấp hơn và cao hơn bằng nhau một cách hiệu quả nhất, ta chỉ cần abs(num_shorter - num_taller) thao tác.

Công thức tính số thao tác tối thiểu:

Tổng số thao tác tối thiểu = (Số bạn có chiều cao bằng H ban đầu phải loại bỏ) + (Số thao tác tối thiểu để cân bằng số lượng bạn thấp hơn và cao hơn Sam)

Số bạn có chiều cao bằng H phải loại bỏ chính là số bạn có chiều cao = H đếm được ở bước 1. Số thao tác tối thiểu để cân bằng chính là abs(num_shorter - num_taller).

Các bước thực hiện trong code (tư duy):

Đọc số test case T.
Lặp T lần:
- Đọc N và H.
- Khởi tạo các biến đếm: shorter_count = 0, taller_count = 0, equal_count = 0.
- Đọc N chiều cao của bạn bè:
  - Với mỗi chiều cao h_friend:
    - Nếu h_friend < H, tăng shorter_count.
    - Nếu h_friend > H, tăng taller_count.
    - Nếu h_friend == H, tăng equal_count.
- Tính số thao tác tối thiểu: min_operations = equal_count + abs(shorter_count - taller_count).
- In min_operations.

Lưu ý khi triển khai:

Sử dụng kiểu dữ liệu phù hợp cho chiều cao (long long hoặc int tùy thuộc vào giới hạn, nhưng int đủ cho $10^9$). Biến đếm có thể dùng int vì N <= $10^5$.
Sử dụng hàm abs() từ thư viện <cmath> (hoặc <cstdlib>).
Đảm bảo đọc hết N chiều cao trước khi tính toán.

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

Comments

There are no comments at the moment.