Что такое priority_queue?

Priority Queue в C++

Priority Queue (приоритетная очередь) — это контейнер-адаптер из STL, который работает как очередь, но извлекает элементы не по принципу FIFO (First-In-First-Out), а в порядке приоритета. По умолчанию элемент с наибольшим значением имеет наивысший приоритет. Priority queue находится в заголовочном файле <queue>.

Внутренняя структура

Priority queue реализуется на основе binary heap (двоичной кучи). Это обеспечивает эффективность операций:

• push() — O(log n)
• pop() — O(log n)
• top() — O(1)

Основные методы

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

std::priority_queue<int> pq;  // По умолчанию: max-heap

// Добавление элемента
pq.push(5);
pq.push(10);
pq.push(3);
pq.push(7);

// Получение элемента с наивысшим приоритетом (максимум)
int top = pq.top();  // Вернёт 10

// Удаление элемента с наивысшим приоритетом
pq.pop();  // Удаляет 10

// Проверка размера и пустоты
size_t size = pq.size();
bool empty = pq.empty();

// Извлечение всех элементов по приоритету
while (!pq.empty()) {
    std::cout << pq.top() << " ";
    pq.pop();
}
// Вывод: 7 5 3

Min-Heap и Max-Heap

По умолчанию priority_queue работает как max-heap (максимальная куча). Для min-heap используют компаратор:

// Max-Heap (по умолчанию)
std::priority_queue<int> maxHeap;
maxHeap.push(5);
maxHeap.push(10);
maxHeap.push(3);
std::cout << maxHeap.top();  // 10

// Min-Heap
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(5);
minHeap.push(10);
minHeap.push(3);
std::cout << minHeap.top();  // 3

// Для пользовательских типов
struct Compare {
    bool operator()(int a, int b) const {
        return a > b;  // min-heap
    }
};

std::priority_queue<int, std::vector<int>, Compare> customHeap;

Работа с объектами

struct Task {
    int priority;
    std::string name;
    
    bool operator<(const Task& other) const {
        return priority < other.priority;  // Для max-heap
    }
};

std::priority_queue<Task> tasks;
tasks.push({3, "Low priority"});
tasks.push({1, "High priority"});
tasks.push({2, "Medium priority"});

while (!tasks.empty()) {
    std::cout << tasks.top().name << std::endl;
    tasks.pop();
}
// Вывод:
// Low priority
// Medium priority
// High priority

Практические примеры

Пример 1: Обслуживание пациентов в больнице

struct Patient {
    std::string name;
    int severity;  // 1 (критичный) - 5 (низкий)
    
    bool operator<(const Patient& other) const {
        return severity > other.severity;  // Сначала более тяжёлые случаи
    }
};

int main() {
    std::priority_queue<Patient> queue;
    queue.push({"Alice", 3});
    queue.push({"Bob", 1});     // Критичный
    queue.push({"Charlie", 5});
    queue.push({"David", 2});
    
    while (!queue.empty()) {
        Patient p = queue.top();
        queue.pop();
        std::cout << p.name << " (severity: " << p.severity << ")" << std::endl;
    }
    
    return 0;
}
// Вывод:
// Bob (severity: 1)
// David (severity: 2)
// Alice (severity: 3)
// Charlie (severity: 5)

Пример 2: Алгоритм Dijkstra (поиск кратчайшего пути)

typedef std::pair<int, int> pii;  // {расстояние, вершина}

void dijkstra(int start, const std::vector<std::vector<pii>>& graph) {
    int n = graph.size();
    std::vector<int> dist(n, INT_MAX);
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;  // Устаревшая информация
        
        for (const auto& [w, v] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

Пример 3: Медиана скользящего потока чисел

class MedianFinder {
private:
    std::priority_queue<int> maxHeap;                    // Левая половина
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;  // Правая половина
    
public:
    void addNum(int num) {
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }
        
        // Балансировка размеров
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

Когда использовать Priority Queue

• Планирование задач — обработка задач по приоритету
• Алгоритмы поиска пути — Dijkstra, Prim
• Системы обработки событий — обработка событий в порядке важности
• Кэширование (LRU) — вытеснение элементов с низким приоритетом
• Обслуживание клиентов — VIP клиенты раньше обычных

Важные особенности

1. Нет случайного доступа — нельзя обратиться к элементу по индексу
2. Быстрый доступ к экстремуму — O(1) для получения максимума/минимума
3. Порядок элементов частичный — heap гарантирует только позицию экстремума
4. Thread-safe нет — при многопоточности нужна синхронизация

Priority queue — это фундаментальная структура данных, необходимая для эффективной реализации множества алгоритмов и систем обработки в режиме реального времени.