Структуры данных для специфичных задач: куча (priority_queue), trie, union-find

Введение

В завершение разбора структур данных рассмотрим три специализированные структуры, каждая решающая конкретный, узкий класс задач значительно эффективнее общих структур: кучу для эффективного доступа к минимуму/максимуму (уже использованную в алгоритме Дейкстры), trie (префиксное дерево) для эффективной работы со строками по общим префиксам, и union-find для эффективного отслеживания принадлежности элементов к непересекающимся группам.

Концепция

Куча (heap) — структура, гарантирующая O(1) доступ к минимальному (или максимальному, в зависимости от типа кучи) элементу и O(log n) для вставки нового элемента или удаления текущего минимума/максимума, реализуемая, как правило, через массив с неявной структурой полного бинарного дерева (без явных указателей между узлами, в отличие от деревьев ) — std::priority_queue предоставляет готовую, стандартную реализацию этой структуры. Trie организует набор строк в дерево, где каждый путь от корня соответствует общему префиксу набора строк, давая эффективный поиск всех строк с заданным префиксом (полезно для автодополнения, статья, упоминавшая поисковые подсказки) значительно быстрее линейного перебора всех строк с проверкой префикса для каждой. Union-find (disjoint set union) эффективно поддерживает разбиение множества элементов на непересекающиеся группы, поддерживая две основные операции — объединение двух групп и определение, принадлежат ли два элемента одной группе, обе почти константной (амортизированной) сложности при правильной реализации с оптимизациями (сжатие пути, объединение по рангу).

Пример кода

// std::priority_queue — куча для задачи "K наибольших элементов" (вариант: K заказов с наибольшей суммой)
#include <queue>

QVector<double> kLargestOrderAmounts(const QVector<double> &allAmounts, int k)
{
    std::priority_queue<double, std::vector<double>, std::greater<>> minHeap; // мин-куча размера k

    for (double amount : allAmounts) {
        minHeap.push(amount);
        if (minHeap.size() > k) {
            minHeap.pop(); // удаляем наименьший — оставляем только k НАИБОЛЬШИХ элементов из всех виденных
        }
    }

    QVector<double> result;
    while (!minHeap.empty()) {
        result.append(minHeap.top());
        minHeap.pop();
    }
    return result; // O(n log k) вместо O(n log n) полной сортировки всех элементов
}

// Trie — эффективный поиск по префиксу (концептуальная реализация для автодополнения)
struct TrieNode {
    std::unordered_map<QChar, std::unique_ptr<TrieNode>> children;
    bool isEndOfWord = false;
};

class Trie {
public:
    void insert(const QString &word) {
        TrieNode *current = &root;
        for (QChar ch : word) {
            if (!current->children.contains(ch)) {
                current->children[ch] = std::make_unique<TrieNode>();
            }
            current = current->children[ch].get();
        }
        current->isEndOfWord = true;
    }

    bool hasPrefix(const QString &prefix) const {
        const TrieNode *current = &root;
        for (QChar ch : prefix) {
            auto it = current->children.find(ch);
            if (it == current->children.end()) return false; // префикс не найден вовсе
            current = it->second.get();
        }
        return true; // дошли до конца префикса — он существует в trie
    }

private:
    TrieNode root;
};

// Union-Find — отслеживание связных компонент (например, группы взаимосвязанных пользователей)
class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i; // изначально каждый элемент — отдельная группа
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // сжатие пути — ускоряет будущие вызовы
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return;
        if (rank[rootX] < rank[rootY]) std::swap(rootX, rootY); // объединение по рангу
        parent[rootY] = rootX;
        if (rank[rootX] == rank[rootY]) rank[rootX]++;
    }

private:
    std::vector<int> parent, rank;
};

Пояснения к коду

kLargestOrderAmounts показывает практичное применение мин-кучи фиксированного размера k для задачи «K наибольших элементов» — поддержание кучи именно размера k (а не полной сортировки всех элементов) даёт сложность O(n log k), что для большого общего количества элементов n и относительно небольшого k значительно эффективнее полной сортировки O(n log n). Trie::hasPrefix проходит ровно по символам искомого префикса, независимо от общего количества хранимых в trie слов — это даёт сложность поиска по префиксу, зависящую только от длины самого префикса, а не от количества слов в коллекции, что принципиально отличается от линейной проверки префикса для каждой строки коллекции отдельно. UnionFind::find с «сжатием пути» (parent[x] = find(parent[x])) — оптимизация, которая при каждом вызове find «выпрямляет» путь до корня группы для всех посещённых при этом вызове элементов, делая будущие вызовы find для этих же элементов значительно быстрее; в сочетании с «объединением по рангу» эта структура достигает почти константной амортизированной сложности для обеих основных операций.

Подводные камни

• Использование std::priority_queue без понимания, что по умолчанию она реализует МАКС-кучу (наибольший элемент сверху), а не мин-кучу — задача, реально требующая эффективного доступа к минимальному элементу (как в реализации алгоритма Дейкстры или в примере kLargestOrderAmounts), требует явного указания std::greater<> как компаратора при создании priority_queue, и забытое указание этого параметра даёт формально работающий, но логически неверный (противоположный нужному) порядок извлечения элементов.
• Реализация trie с хранением всех возможных детей узла через массив фиксированного размера (например, размером алфавита) вместо unordered_map, как в примере, для случаев со значительно более широким диапазоном возможных символов (Unicode, а не только ASCII-алфавит) — фиксированный по размеру массив для каждого узла при широком диапазоне возможных символов тратит огромное количество памяти на преимущественно пустые, неиспользуемые ячейки, и для таких случаев unordered_map, хранящий только реально присутствующие переходы, значительно эффективнее по памяти, хотя и немного медленнее по константе доступа к отдельному переходу.
• Реализация Union-Find без обеих ключевых оптимизаций (сжатие пути и объединение по рангу/размеру) — без этих оптимизаций структура остаётся корректной по своей базовой логике, но может деградировать до O(n) для отдельных операций в худшем случае (длинная, невыпрямленная цепочка родителей), тогда как с обеими оптимизациями достигается почти константная амортизированная сложность — пропуск этих, относительно простых для реализации оптимизаций существенно меняет практическую применимость структуры для больших наборов данных.
• Применение специализированной структуры данных (куча, trie, union-find) для задачи, где более простая, общая структура решает ту же задачу не менее эффективно на практике — каждая из этих специализированных структур добавляет определённую сложность реализации и понимания по сравнению с более общими структурами, и эта дополнительная сложность оправдана только реальной потребностью в её специфичных, узких преимуществах (как поиск по префиксу для trie или эффективное определение принадлежности к группе для union-find), а не использованием «потому что это более продвинутая структура данных».