k-Largest dan k-Smallest

Mencari k elemen terbesar atau terkecil dari koleksi n elemen adalah masalah yang sering muncul: top-10 produk terlaris, top-100 query pencarian, top-k pengguna dengan aktivitas tertinggi. Pendekatan naif mengurutkan seluruh data dalam O(n log n) — boros bila k ≪ n. Heap berukuran k memberi solusi O(n log k) yang jauh lebih murah untuk k kecil, dan STL juga menyediakan std::nth_element yang rata-rata O(n) untuk partial sort. Pada Chapter ini kita akan membedah tiga strategi (full sort, heap of size k, nth_element), mengimplementasikan masing-masing, dan membandingkan performanya secara empiris. Pada akhir chapter kita akan paham kapan memilih strategi mana berdasarkan k relatif terhadap n.

Tiga Strategi Pencarian k Elemen #

Strategi 1: Heap Berukuran k #

Aturan: Pertahankan Heap Berukuran k #

Untuk mencari k elemen terbesar:

• Gunakan min-heap berukuran k.
• Iterasi setiap elemen: bila heap belum penuh (size < k), langsung push. Bila sudah penuh dan elemen baru lebih besar dari root (elemen minimum di heap), ganti root dengan pop lalu push.

Mengapa min-heap? Root menyimpan batas bawah dari k elemen terbesar yang sudah dikumpulkan — elemen ke-k terbesar. Elemen baru yang lebih kecil dari batas ini langsung diabaikan.

Sebaliknya, untuk mencari k elemen terkecil:

• Gunakan max-heap berukuran k.
• Bila elemen baru lebih kecil dari root (elemen maksimum di heap), ganti root.

Mekanisme: Mengapa Heap Berukuran k Cukup #

Setiap elemen baru hanya dibandingkan dengan root (satu operasi O(1)) — bila tidak lolos, tidak ada operasi heap. Bila lolos, sekali pop + push (O(log k)). Total worst case O(n log k), namun rata-rata O(n + n · p · log k) di mana p adalah probabilitas lolos (≈ k/n), sehingga rata-rata ≈ O(n + k log k · log k) ≈ O(n) untuk k ≪ n.

Kode: Heap Berukuran k dan nth_element #

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <chrono>
#include <random>

// k largest: min-heap berukuran k
std::vector<int> k_largest_heap(const std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minH;
    for (int x : nums) {
        if (static_cast<int>(minH.size()) < k) {
            minH.push(x);
        } else if (x > minH.top()) {
            minH.pop();
            minH.push(x);
        }
    }
    std::vector<int> res;
    while (!minH.empty()) { res.push_back(minH.top()); minH.pop(); }
    std::sort(res.rbegin(), res.rend());  // descending
    return res;
}

// k smallest: max-heap berukuran k
std::vector<int> k_smallest_heap(const std::vector<int>& nums, int k) {
    std::priority_queue<int> maxH;
    for (int x : nums) {
        if (static_cast<int>(maxH.size()) < k) {
            maxH.push(x);
        } else if (x < maxH.top()) {
            maxH.pop();
            maxH.push(x);
        }
    }
    std::vector<int> res;
    while (!maxH.empty()) { res.push_back(maxH.top()); maxH.pop(); }
    std::sort(res.begin(), res.end());  // ascending
    return res;
}

// Alternatif: std::nth_element O(n) average
std::vector<int> k_largest_nth(const std::vector<int>& nums, int k) {
    std::vector<int> v = nums;
    int n = static_cast<int>(v.size());
    std::nth_element(v.begin(), v.begin() + (n - k), v.end());
    std::sort(v.begin() + (n - k), v.end(), std::greater<int>());
    return std::vector<int>(v.begin() + (n - k), v.end());
}

int main() {
    std::vector<int> nums = {3, 1, 5, 7, 2, 8, 4, 6, 9, 0};
    int k = 3;

    auto lg = k_largest_heap(nums, k);
    std::cout << k << " largest  (heap): ";
    for (int x : lg) std::cout << x << ' ';
    std::cout << '\n';

    auto sm = k_smallest_heap(nums, k);
    std::cout << k << " smallest (heap): ";
    for (int x : sm) std::cout << x << ' ';
    std::cout << '\n';

    auto lg2 = k_largest_nth(nums, k);
    std::cout << k << " largest  (nth) : ";
    for (int x : lg2) std::cout << x << ' ';
    std::cout << '\n';

    // Benchmark pada data besar
    constexpr int N = 10'000'000;
    std::mt19937 rng(42);
    std::vector<int> big(N);
    for (int i = 0; i < N; ++i) big[i] = static_cast<int>(rng());

    int K = 100;
    auto t1 = std::chrono::high_resolution_clock::now();
    auto h = k_largest_heap(big, K);
    auto t2 = std::chrono::high_resolution_clock::now();
    auto n = k_largest_nth(big, K);
    auto t3 = std::chrono::high_resolution_clock::now();
    std::sort(big.rbegin(), big.rend());
    auto t4 = std::chrono::high_resolution_clock::now();

    std::cout << "\nBenchmark N=" << N << ", k=" << K << ":\n";
    std::cout << "  heap         : "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << " ms\n";
    std::cout << "  nth_element  : "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count() << " ms\n";
    std::cout << "  full sort    : "
              << std::chrono::duration_cast<std::chrono::milliseconds>(t4 - t3).count() << " ms\n";
    return 0;
}

Output yang Dihasilkan:

3 largest  (heap): 9 8 7 
3 smallest (heap): 0 1 2 
3 largest  (nth) : 9 8 7 

Benchmark N=10000000, k=100:
  heap         : 9 ms
  nth_element  : 86 ms
  full sort    : 740 ms

Bedah Kode Baris-per-Baris #

1. std::priority_queue<int, std::vector<int>, std::greater<int>> minH;: min-heap int. Root = elemen terkecil di heap = batas bawah k elemen terbesar yang sudah dikumpulkan.
2. if (static_cast<int>(minH.size()) < k): bila heap belum penuh (size < k), push langsung tanpa perbandingan. Fase pengisian awal k elemen pertama.
3. else if (x > minH.top()): bila heap sudah penuh dan elemen baru x lebih besar dari root (elemen minimum di k terbesar saat ini), x layak masuk ke k terbesar.
4. minH.pop(); minH.push(x);: buang root lama (tidak masuk k terbesar), tambah x. Catatan: bisa juga pakai replace(x) bila implementasi mendukung — 1 sift down vs 2.
5. std::sort(res.rbegin(), res.rend());: pop menghasilkan elemen ascending (karena min-heap), rbegin/rend untuk descending.
6. std::priority_queue<int> maxH;: max-heap (default). Untuk k smallest, root = elemen terbesar di heap = batas atas k elemen terkecil.
7. else if (x < maxH.top()): bila x lebih kecil dari batas atas, x layak masuk k terkecil.
8. std::nth_element(v.begin(), v.begin() + (n - k), v.end());: partisi sehingga elemen ke-(n-k) (dalam urutan terurut) berada pada posisinya yang benar. Semua elemen di kiri lebih kecil, semua di kanan lebih besar. Hanya elemen [n-k, n) yang menjadi k terbesar.
9. std::sort(v.begin() + (n - k), v.end(), std::greater<int>());: urutkan slice k terbesar descending.
10. Output: ketiga strategi menghasilkan jawaban yang sama (9 8 7), namun performa berbeda jauh.
11. Benchmark: heap 9 ms, nth_element 86 ms, full sort 740 ms. Untuk k = 100 dan n = 10 juta, heap menang karena n log k = 10M × 7 = 70M operasi vs nth_element yang O(n) namun dengan konstanta tinggi (pivoting + multiple passes). Full sort jelas paling lambat.

Kapan Heap Menang, Kapan nth_element #

Hasil benchmark di atas mungkin terkesan kontra-intuitif — nth_element seharusnya O(n) tapi kalah dari heap. Alasannya: untuk k kecil, O(n log k) bisa lebih cepat dari O(n) karena konstanta operasi heap sangat rendah (sekali perbandingan + occasional swap).

Pedoman umum:

Strategi 3: Stream dengan Heap #

Keunggulan utama heap berukuran k: dapat memproses stream data yang tidak muat di memori. Bandingkan dengan nth_element yang membutuhkan seluruh data tersedia sekaligus.

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

class StreamingTopK {
    int k;
    std::priority_queue<int, std::vector<int>, std::greater<int>> minH;
public:
    explicit StreamingTopK(int k_) : k(k_) {}

    void add(int x) {
        if (static_cast<int>(minH.size()) < k) {
            minH.push(x);
        } else if (x > minH.top()) {
            minH.pop();
            minH.push(x);
        }
    }

    std::vector<int> result() const {
        auto copy = minH;          // copy karena priority_queue pop merusak
        std::vector<int> res;
        while (!copy.empty()) { res.push_back(copy.top()); copy.pop(); }
        std::sort(res.rbegin(), res.rend());
        return res;
    }
};

int main() {
    StreamingTopK stk(3);
    // Simulasi stream: data datang satu per satu
    int stream[] = {3, 1, 5, 7, 2, 8, 4, 6, 9, 0};
    for (int x : stream) {
        stk.add(x);
        std::cout << "add " << x << " -> top-3: ";
        for (int v : stk.result()) std::cout << v << ' ';
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

add 3 -> top-3: 3 
add 1 -> top-3: 3 1 
add 5 -> top-3: 5 3 1 
add 7 -> top-3: 7 5 3 
add 2 -> top-3: 7 5 3 
add 8 -> top-3: 8 7 5 
add 4 -> top-3: 8 7 5 
add 6 -> top-3: 8 7 6 
add 9 -> top-3: 9 8 7 
add 0 -> top-3: 9 8 7 

Bedah Kode Baris-per-Baris #

1. explicit StreamingTopK(int k_) : k(k_) {}: konstruktor dengan explicit untuk menghindari implicit conversion dari int. Heap ukuran k dialokasikan kosong.
2. void add(int x): tambah satu elemen stream. Bila heap belum penuh, langsung push. Bila sudah penuh dan x lebih besar dari root, ganti root.
3. std::vector<int> result() const: snapshot k elemen terbesar saat ini. Method const namun membuat copy karena pop menghapus elemen. Untuk produksi, simpan container terpisah agar tidak perlu copy.
4. Output: terlihat evolusi top-3 sepanjang stream. Setelah add 5 heap berisi {5, 3, 1} (root = 1). Setelah add 7, 7 > 1 sehingga pop 1 push 7 → {7, 5, 3}. Setelah semua stream diproses, top-3 stabil di {9, 8, 7}.

Varian: Top-k Frequent Elements #

Varian umum: temukan k elemen dengan frekuensi terbanyak. Strategi:

1. Hitung frekuensi dengan std::unordered_map (O(n)).
2. Iterasi map, pertahankan min-heap berukuran k berisi pair<frequency, value>.
3. Pop akhir untuk mengambil k elemen terbanyak.

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>

std::vector<std::pair<int, std::string>> top_k_frequent(
        const std::vector<std::string>& words, int k) {
    std::unordered_map<std::string, int> freq;
    for (const auto& w : words) freq[w]++;

    using P = std::pair<int, std::string>;  // (freq, word)
    auto cmp = [](const P& a, const P& b) {
        if (a.first != b.first) return a.first > b.first;  // freq lebih besar = lebih dekat ke root (max-heap)
        return a.second < b.second;                       // tiebreak: lexicographic
    };
    // min-heap berdasarkan freq: elemen dengan freq kecil = root
    std::priority_queue<P, std::vector<P>, decltype(cmp)> pq(cmp);
    for (const auto& [w, f] : freq) {
        pq.push({f, w});
        if (static_cast<int>(pq.size()) > k) pq.pop();
    }

    std::vector<P> res;
    while (!pq.empty()) { res.push_back(pq.top()); pq.pop(); }
    std::sort(res.begin(), res.end(), [](const P& a, const P& b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });
    return res;
}

int main() {
    std::vector<std::string> words = {"the", "day", "is", "sunny",
                                       "the", "the", "sunny", "is", "is"};
    int k = 2;
    auto top = top_k_frequent(words, k);
    std::cout << "Top-" << k << " frequent:\n";
    for (const auto& [f, w] : top) {
        std::cout << "  " << w << " (" << f << "x)\n";
    }
    return 0;
}

Output yang Dihasilkan:

Top-2 frequent:
  is (3x)
  the (3x)

Bedah Kode Baris-per-Baris #

1. std::unordered_map<std::string, int> freq;: hitung frekuensi setiap kata. Kompleksitas O(n) rata-rata.
2. using P = std::pair<int, std::string>;: alias untuk pair (freq, word). freq di posisi pertama agar pair comparator default membandingkan freq lebih dulu.
3. auto cmp = [](...) { ... }: comparator custom. Bila frekuensi berbeda, freq lebih besar = “lebih besar” → menjadi root pada min-heap (akan di-pop pertama). Bila frekuensi sama, lexicographic tiebreak.
4. pq.push({f, w}); if (pq.size() > k) pq.pop();: push semua elemen, lalu pop bila size melebihi k. Setelah iterasi, queue berisi k elemen dengan frekuensi tertinggi.
5. std::sort(res.begin(), res.end(), ...): urutkan hasil descending berdasarkan frekuensi (lalu lexicographic untuk tiebreak).
6. Output: is dan the sama-sama muncul 3 kali — keduanya masuk top-2. Tiebreak lexicographic: is < the, urutan output is lalu the.

Komparasi Akhir Strategi #

Ringkasan #

• Untuk k ≪ n, heap berukuran k memberi O(n log k) dan O(k) memori — paling efisien.
• Min-heap untuk k largest (root = batas bawah k terbesar), max-heap untuk k smallest (root = batas atas k terkecil).
• std::nth_element rata-rata O(n) namun membutuhkan seluruh data tersedia sekaligus.
• Heap berukuran k adalah satu-satunya pilihan untuk streaming data.
• Untuk top-k frequent: gunakan unordered_map + heap berukuran k.
• Pemilihan strategi: heap untuk k < n/100 atau streaming; nth_element untuk k besar dengan data statis.

Pada Chapter berikutnya kita akan mengaplikasikan heap untuk masalah klasik lain: menggabungkan k array terurut menjadi satu array terurut dengan kompleksitas O(n log k).