Menggabungkan k array terurut menjadi satu array terurut adalah masalah klasik yang muncul di external sorting, distributed systems (merge shard), dan algoritma divide-and-conquer. Pendekatan naif menggabungkan berpasangan atau langsung menggabungkan seluruh elemen lalu sort — keduanya suboptimal. Dengan min-heap berukuran k, kita dapat menggabungkan dalam O(n log k) di mana n adalah total elemen dan k adalah jumlah array — signifikan lebih cepat dari O(n log n) ketika k ≪ n. Pada Chapter ini kita akan membedah mekanisme merge dengan heap, mengimplementasikan algoritma lengkap, dan membahas varian lanjutan untuk external sorting dan linked list. Pada akhir chapter kita akan punya pola yang dapat diterapkan ke banyak masalah merge serupa.

Aturan: Merge k Sorted Arrays #

Diberikan k array A₁, A₂, ..., Aₖ yang masing-masing sudah terurut ascending. Gabungkan menjadi satu array R yang terurut ascending pula, dengan kompleksitas waktu O(n log k) dan ruang O(k) tambahan, di mana n = |A₁| + |A₂| + ... + |Aₖ|.

Mekanisme: Min-Heap Berisi Kandidat Terkecil Berikutnya #

Inti algoritma: setiap saat, elemen terkecil berikutnya pada hasil adalah salah satu dari elemen pertama (head) setiap array yang belum diambil. Karena hanya ada k kandidat, gunakan min-heap berukuran k untuk melacak kandidat terkecil secara efisien.

Kompleksitas #

  • Inisialisasi: push k elemen pertama → O(k log k).
  • Loop utama: n kali extract-min + push (bila array sumber belum habis), masing-masing O(log k) → O(n log k).
  • Total: O((n + k) log k) = O(n log k) untuk n ≫ k.

Kode: Merge k Sorted Arrays #

cpp 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>

// Menggabungkan k array terurut menjadi satu array terurut.
// Kompleksitas: O(n log k), n = total elemen, k = jumlah array.
std::vector<int> merge_k_sorted(const std::vector<std::vector<int>>& arrays) {
    using P = std::pair<int, std::pair<int, int>>;  // (value, (array_idx, elem_idx))
    auto cmp = [](const P& a, const P& b) { return a.first > b.first; };  // min-heap by value
    std::priority_queue<P, std::vector<P>, decltype(cmp)> pq(cmp);

    // Inisialisasi: push elemen pertama dari setiap array
    for (int i = 0; i < static_cast<int>(arrays.size()); ++i) {
        if (!arrays[i].empty()) {
            pq.push({arrays[i][0], {i, 0}});
        }
    }

    std::vector<int> result;
    while (!pq.empty()) {
        auto [val, idx] = pq.top();
        pq.pop();
        result.push_back(val);

        int arr = idx.first, pos = idx.second + 1;
        if (pos < static_cast<int>(arrays[arr].size())) {
            pq.push({arrays[arr][pos], {arr, pos}});
        }
    }
    return result;
}

int main() {
    std::vector<std::vector<int>> arrays = {
        {1, 4, 7, 10},
        {2, 5, 8, 11, 14},
        {3, 6, 9, 12},
        {0, 13, 15}
    };

    std::cout << "Input k = " << arrays.size() << " array:\n";
    for (int i = 0; i < static_cast<int>(arrays.size()); ++i) {
        std::cout << "  arr" << i << ": ";
        for (int x : arrays[i]) std::cout << x << ' ';
        std::cout << '\n';
    }

    auto merged = merge_k_sorted(arrays);
    std::cout << "\nMerged: ";
    for (int x : merged) std::cout << x << ' ';
    std::cout << '\n';

    // Verifikasi urutan
    bool sorted = std::is_sorted(merged.begin(), merged.end());
    std::cout << "Terurut ascending? " << std::boolalpha << sorted << '\n';

    return 0;
}

Output yang Dihasilkan:

text 
Input k = 4 array:
  arr0: 1 4 7 10 
  arr1: 2 5 8 11 14 
  arr2: 3 6 9 12 
  arr3: 0 13 15 

Merged: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
Terurut ascending? true

Bedah Kode Baris-per-Baris #

  1. using P = std::pair<int, std::pair<int, int>>;: alias tipe untuk tuple (value, (array_idx, elem_idx)). value di posisi pertama agar comparator default pair membandingkan value lebih dulu.
  2. auto cmp = [](const P& a, const P& b) { return a.first > b.first; };: lambda comparator untuk min-heap. Kembalikan true bila a.first > b.first — artinya a harus berada di bawah b, sehingga elemen terkecil berada di top.
  3. std::priority_queue<P, std::vector<P>, decltype(cmp)> pq(cmp);: min-heap dengan comparator lambda. Perhatikan argumen konstruktor cmp — diperlukan karena lambda tidak default-constructible sebelum C++20.
  4. for (int i = 0; i < ...; ++i) if (!arrays[i].empty()) pq.push({arrays[i][0], {i, 0}});: inisialisasi — push elemen pertama (indeks 0) dari setiap array yang tidak kosong. Heap kini berisi ≤ k kandidat awal.
  5. auto [val, idx] = pq.top(); pq.pop();: ambil elemen terkecil (root heap). Structured binding mengurai pair menjadi val (nilai) dan idx (pasangan array_idx, elem_idx).
  6. result.push_back(val);: tambahkan ke hasil. Karena val adalah elemen terkecil di antara seluruh kandidat yang tersisa, urutan ascending terjaga.
  7. int arr = idx.first, pos = idx.second + 1;: posisi elemen berikutnya pada array sumber yang sama.
  8. if (pos < static_cast<int>(arrays[arr].size())) pq.push({arrays[arr][pos], {arr, pos}});: bila array sumber masih punya elemen berikutnya, push ke heap. Bila sudah habis, jangan push — heap mengecil, dan inilah mengapa ukuran heap bisa kurang dari k sepanjang iterasi.
  9. Output: hasil terurut ascending 0 1 2 ... 15 — 16 elemen total dari 4 array. Verifikasi std::is_sorted mengembalikan true.

Perbandingan dengan Strategi Lain #

Strategi 1: Concatenate + Sort #

Cara paling sederhana: gabungkan seluruh elemen ke satu vector, lalu sort.

cpp 
std::vector<int> merge_concat_sort(const std::vector<std::vector<int>>& arrays) {
    std::vector<int> result;
    for (const auto& arr : arrays) result.insert(result.end(), arr.begin(), arr.end());
    std::sort(result.begin(), result.end());
    return result;
}

Kompleksitas: O(n log n). Sederhana namun mengabaikan keterterutan array masukan — pekerjaan yang sudah dilakukan hilang.

Strategi 2: Merge Berpasangan (Divide and Conquer) #

Gabungkan pasangan array berurutan, lalu gabungkan hasilnya, hingga tersisa satu array (mirip merge sort).

cpp 
std::vector<int> merge_two(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> r;
    size_t i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        r.push_back(a[i] <= b[j] ? a[i++] : b[j++]);
    }
    r.insert(r.end(), a.begin() + i, a.end());
    r.insert(r.end(), b.begin() + j, b.end());
    return r;
}

std::vector<int> merge_k_pairwise(const std::vector<std::vector<int>>& arrays) {
    if (arrays.empty()) return {};
    std::vector<std::vector<int>> work = arrays;
    while (work.size() > 1) {
        std::vector<std::vector<int>> next;
        for (size_t i = 0; i < work.size(); i += 2) {
            if (i + 1 < work.size()) next.push_back(merge_two(work[i], work[i+1]));
            else next.push_back(work[i]);
        }
        work = std::move(next);
    }
    return work.front();
}

Kompleksitas: O(n log k) — sama dengan heap, namun ruang tambahan O(n) (intermediate arrays). Lebih cocok untuk linked list daripada array dinamis.

Tabel Komparasi #

StrategiTimeSpace TambahanCatatan
Concatenate + sortO(n log n)O(n)Sederhana, abaikan sorted input
Heap berukuran kO(n log k)O(k)Optimal untuk array
Pairwise mergeO(n log k)O(n)Cocok untuk linked list

Varian: Merge k Sorted Linked Lists #

Untuk linked list, strategi pairwise merge lebih efisien karena merge_two pada linked list tidak menyalin elemen — hanya mengubah pointer next. Untuk heap, kita perlu menyimpan pointer ke node, namun alokasi heap pair<value, ListNode*> tetap berbiaya O(k).

cpp 
struct ListNode {
    int val;
    ListNode* next;
};

struct ListNodeCmp {
    bool operator()(const ListNode* a, const ListNode* b) const {
        return a->val > b->val;  // min-heap
    }
};

ListNode* merge_k_lists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, ListNodeCmp> pq;
    for (ListNode* h : lists) if (h) pq.push(h);

    ListNode dummy{0, nullptr};
    ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* n = pq.top();
        pq.pop();
        tail->next = n;
        tail = n;
        if (n->next) pq.push(n->next);
    }
    tail->next = nullptr;
    return dummy.next;
}

Pointer-based: tidak ada salinan data, hanya pointer yang dimanipulasi. Kompleksitas tetap O(n log k) waktu, O(k) ruang.

Aplikasi: External Sorting #

External sorting mengurutkan data yang tidak muat di memori. Strategi:

  1. Split — bagi file besar menjadi k run (chunk) yang masing-masing muat di memori.
  2. Sort each run — urutkan tiap chunk di memori, tulis kembali ke disk sebagai file terurut.
  3. k-way merge — gabungkan k file terurut dengan algoritma di atas.

Heap berukuran k sangat penting di sini — buffer I/O hanya perlu k elemen aktif, bukan n. Tanpa heap, harus dibaca seluruh elemen ke memori (mustahil bila n sangat besar).

Aplikasi: Distributed MapReduce Shuffle #

Pada MapReduce, reducer menerima data dari banyak mapper yang masing-masing sudah terurut lokal. Reducer melakukan k-way merge untuk menggabungkan input-input ini menjadi satu stream terurut sebelum diproses. Algoritma merge-k-sorted adalah inti dari shuffle-and-sort phase MapReduce.

Edge Cases #

Array Kosong #

Kode di atas sudah menangani array kosong — if (!arrays[i].empty()) memastikan tidak ada push elemen dari array kosong.

Satu Array Saja #

Bila k = 1, algoritma tetap bekerja namun overhead heap tidak perlu. Optimalisasi: bila k = 1, langsung kembalikan array tersebut.

Semua Array Identik #

Bila semua array berisi elemen yang sama, algoritma tetap benar — heap mengandung k pointer ke elemen yang sama, extract menghasilkan elemen yang sama n kali.

Optimisasi Lanjutan #

K-way Merge dengan Heap In-Place #

Untuk array yang dapat dimodifikasi (mutable), kita bisa menggunakan arrays itu sendiri sebagai memori output — overwrite satu array dengan hasil akhir. Strategi ini mengurangi penggunaan memori namun rumit secara indeks.

Penggunaan Iterator #

Daripada menyimpan indeks (array_idx, elem_idx), gunakan iterator C++:

cpp 
struct It {
    int val;
    std::vector<int>::const_iterator it, end;
    bool operator>(const It& o) const { return val > o.val; }
};
std::priority_queue<It, std::vector<It>, std::greater<It>> pq;

Pendekatan ini lebih idiomatik C++ namun membutuhkan struct custom.

Komparasi dengan std::inplace_merge #

STL memiliki std::inplace_merge untuk merge dua range terurut. Untuk k > 2, STL tidak menyediakan fungsi langsung — kita harus mengimplementasikan sendiri dengan heap atau memanggil std::inplace_merge berpasangan (strategi pairwise).

Ringkasan #

  • Merge k sorted arrays dengan heap: O(n log k) waktu, O(k) ruang tambahan.
  • Strategi: push elemen pertama setiap array ke min-heap, extract-min, push elemen berikutnya dari array sumber.
  • Lebih efisien daripada concatenate + sort (O(n log n)) bila k ≪ n.
  • Varian linked list menggunakan pointer ke node — tidak ada salinan data.
  • Aplikasi: external sorting, MapReduce shuffle, distributed merge.
  • Edge cases: array kosong, k = 1, semua array identik.

Pada Chapter berikutnya kita akan menutup Section 14 dengan tinjauan komprehensif penerapan heap di berbagai algoritma dan struktur data lanjutan: Dijkstra, Prim, median of stream, dan scheduling.