Тренды

C++: практическое руководство по priority_queue

23.01.2025

priority_queue: базовое применение

Контейнером-адаптером priority_queue на C++ поддерживается коллекция элементов, на верху которой всегда оказывается элемент с наивысшим приоритетом. Начнем с простого примера:

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    
    pq.push(30);
    pq.push(100);
    pq.push(25);
    pq.push(40);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    // Вывод: 100 40 30 25

    return 0;
}

По умолчанию в priority_queue в качестве функции сравнения применяется std::less, так получается куча с максимумом.

Создание кучи с минимумом

Куча с минимумом создается при помощи std::greater:

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

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    
    min_pq.push(30);
    min_pq.push(100);
    min_pq.push(25);
    min_pq.push(40);

    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    // Вывод: 25 30 40 100

    return 0;
}

Так создается приоритизированная очередь, на верху которой всегда оказывается минимальный элемент.

Пользовательские типы

Указав функцию сравнения, применим priority_queue с пользовательскими типами:

#include <iostream>
#include <queue>
#include <string>

struct Task {
    int priority;
    std::string name;

    Task(int p, std::string n) : priority(p), name(std::move(n)) {}
};

struct CompareTask {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority;
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> task_queue;

    task_queue.emplace(3, "Write report");
    task_queue.emplace(1, "Fix critical bug");
    task_queue.emplace(2, "Prepare presentation");

    while (!task_queue.empty()) {
        const Task& task = task_queue.top();
        std::cout << "Priority: " << task.priority << ", Task: " << task.name << std::endl;
        task_queue.pop();
    }

    return 0;
}

В этом примере priority_queue применяется с пользовательской структурой Task, которой приоритизируются задачи по их значению приоритета.

Изменение элементов в priority_queue

Одно из ограничений priority_queue — невозможность напрямую изменить его элементы. Но оно преодолевается указателями:

#include <iostream>
#include <queue>
#include <memory>

struct Item {
    int priority;
    std::string name;

    Item(int p, std::string n) : priority(p), name(std::move(n)) {}
};

struct CompareItem {
    bool operator()(const std::shared_ptr<Item>& i1, const std::shared_ptr<Item>& i2) {
        return i1->priority < i2->priority;
    }
};

int main() {
    std::priority_queue<std::shared_ptr<Item>, std::vector<std::shared_ptr<Item>>, CompareItem> item_queue;

    auto item1 = std::make_shared<Item>(2, "Item 1");
    auto item2 = std::make_shared<Item>(1, "Item 2");

    item_queue.push(item1);
    item_queue.push(item2);

    // Меняем приоритет элемента «item2»
    item2->priority = 3;

    // Вставляем элемент «item2» заново, обновляя так его положение
    item_queue.push(item2);

    while (!item_queue.empty()) {
        auto item = item_queue.top();
        std::cout << "Priority: " << item->priority << ", Name: " << item->name << std::endl;
        item_queue.pop();
    }

    return 0;
}

Таким подходом изменяются элементы, обновляется их положение в очереди.

Реальный сценарий: планировщик процессов

Реализуем с priority_queue простой планировщик процессов:

#include <iostream>
#include <queue>
#include <string>
#include <iomanip>

struct Process {
    int priority;
    std::string name;
    int burst_time;

    Process(int p, std::string n, int bt) : priority(p), name(std::move(n)), burst_time(bt) {}
};

struct CompareProcess {
    bool operator()(const Process& p1, const Process& p2) {
        return p1.priority < p2.priority;
    }
};

class Scheduler {
private:
    std::priority_queue<Process, std::vector<Process>, CompareProcess> process_queue;

public:
    void add_process(int priority, const std::string& name, int burst_time) {
        process_queue.emplace(priority, name, burst_time);
    }

    void run() {
        int total_time = 0;
        std::cout << std::left << std::setw(15) << "Process" << std::setw(10) << "Priority" 
                  << std::setw(15) << "Burst Time" << std::setw(15) << "Start Time" << std::endl;

        while (!process_queue.empty()) {
            Process current_process = process_queue.top();
            process_queue.pop();

            std::cout << std::left << std::setw(15) << current_process.name 
                      << std::setw(10) << current_process.priority
                      << std::setw(15) << current_process.burst_time
                      << std::setw(15) << total_time << std::endl;

            total_time += current_process.burst_time;
        }
    }
};

int main() {
    Scheduler scheduler;

    scheduler.add_process(3, "Process A", 5);
    scheduler.add_process(1, "Process B", 3);
    scheduler.add_process(4, "Process C", 2);
    scheduler.add_process(2, "Process D", 4);

    scheduler.run();

    return 0;
}

Этим планировщиком с priority_queue процессы управляются по их приоритету, так приоритизированные очереди применяются в операционных системах.

Сочетание priority_queue с другими STL-контейнерами

Для более сложного управления данными priority_queue сочетают с другими контейнерами стандартной библиотеки шаблонов:

#include <iostream>
#include <queue>
#include <map>
#include <string>

int main() {
    std::map<std::string, std::priority_queue<int>> scores;

    scores["Alice"].push(85);
    scores["Alice"].push(92);
    scores["Bob"].push(76);
    scores["Alice"].push(88);
    scores["Bob"].push(95);

    for (const auto& [name, pq] : scores) {
        std::cout << name << "'s top score: " << pq.top() << std::endl;
    }

    return 0;
}

В этом примере результаты игроков отслеживаются картой приоритизированных очередей.

Производительность

В priority_queue для операций вставки и удаления обеспечивается временна́я сложность O(log n), а для доступа к верхнему элементу — O(1). Хотя для очень больших наборов данных или частых изменений имеются альтернативы:

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

const int NUM_ELEMENTS = 1000000;

void benchmark_priority_queue() {
    std::priority_queue<int> pq;
    
    auto start = std::chrono::high_resolution_clock::now();
    
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        pq.push(i);
    }
    
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        pq.pop();
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end - start;
    
    std::cout << "priority_queue time: " << diff.count() << " seconds" << std::endl;
}

void benchmark_sorted_vector() {
    std::vector<int> vec;
    
    auto start = std::chrono::high_resolution_clock::now();
    
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        vec.push_back(i);
        std::push_heap(vec.begin(), vec.end());
    }
    
    for (int i = 0; i < NUM_ELEMENTS; ++i) {
        std::pop_heap(vec.begin(), vec.end());
        vec.pop_back();
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> diff = end - start;
    
    std::cout << "Sorted vector time: " << diff.count() << " seconds" << std::endl;
}

int main() {
    benchmark_priority_queue();
    benchmark_sorted_vector();
    
    return 0;
}

В этом тесте priority_queue сравнивается с кучей, управляемой вручную при помощи вектора. Что выполняется оптимальнее? Узнайте, запустив это у себя в системе.

Типичные ошибки и как их избежать

Изменить элементы напрямую, пока они в очереди, нельзя. Чтобы обновить приоритеты, воспользуйтесь приемом с указателями.
Упорядоченная итерация в priority_queue не предусмотрена. Чтобы обработать все элементы по порядку, извлекайте их один за другим.
До вызова top() или pop() всегда проверяйте, не пуста ли очередь.
Недопонимание функции сравнения. Ею определяется строгое слабое упорядочение, убедитесь в соответствии пользовательских компараторов этому требованию.
Упускается из виду использование памяти. В priority_queue хранится копия вставленных элементов, для больших объектов воспользуйтесь указателями или ссылками.

Заключение

Адаптером-контейнером priority_queue на C++ эффективно управляются приоритизированные данные. Это гибкое решение для многих программных сценариев — от простых числовых приоритетов до сложных пользовательских объектов.

priority_queue оптимизирован для быстрого доступа к элементу с наивысшим приоритетом, но ограничен при изменении других элементов или доступе к ним.

Чтобы осуществлять более сложное управление приоритетами, priority_queue сочетают с другими структурами данных или реализуют собственную приоритизированную очередь.

C++: практическое руководство по priority_queue

priority_queue: базовое применение

Создание кучи с минимумом

Пользовательские типы

Изменение элементов в priority_queue

Реальный сценарий: планировщик процессов

Сочетание priority_queue с другими STL-контейнерами

Производительность

Типичные ошибки и как их избежать

Заключение

Читайте также

Эволюция кортежей в C#

Как сделать интеллектуальное приложение вопросов и ответов базы знаний с GPT-3...

Решение крупномасштабных задач машинного обучения на Python

Тесты

Насколько хорошо вы разбираетесь в Python?

Что вы знаете о языке C++

Насколько хорошо вы знакомы с Mac?