Алгоритм Прима на куче vs Краскал — когда какой выбрать для MST?

Прим растит дерево из одной вершины: на каждом шаге добавляет самое лёгкое ребро, выходящее из уже построенного дерева наружу. С бинарной кучей:

long long prim(int n, vector<pair<int,int>> g[]) { // g[v] = {вес, сосед}... храните как {сосед, вес}
    vector<bool> in(n, false);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    pq.push({0, 0});
    long long cost = 0; int taken = 0;
    while (!pq.empty() && taken < n) {
        auto [w, v] = pq.top(); pq.pop();
        if (in[v]) continue;       // ленивое удаление дубликатов
        in[v] = true; cost += w; taken++;
        for (auto [u, wu] : g[v]) if (!in[u]) pq.push({wu, u});
    }
    return cost;
}

Сложность Прима на куче: O(E log V). Краскал: O(E log E) = O(E log V) (т.к. log E ≤ 2 log V). Асимптотически одинаково.

Когда что:

• Граф задан списком рёбер и/или разрежен (E ≈ V) — берите Краскал, он проще и СНМ быстр.
• Граф плотный (E ≈ V²), например полный граф на координатах — берите Прима на массиве (без кучи) за O(V²), это быстрее, чем E log V ≈ V² log V.
• Нужен MST с восстановлением рёбер или поддержка онлайн-добавления — Краскал + СНМ удобнее.

Память обоих O(V+E).