Blank page

Для реализации очереди с приоритетом, где максимальный элемент всегда находится в начале, можно использовать структуру данных "куча" (heap). В C++ есть стандартная библиотека <algorithm>, которая предоставляет функции для работы с кучей: std::make_heap, std::push_heap и std::pop_heap. Мы будем использовать эти функции для реализации простой очереди с приоритетом.
Вот пример программы:

#include <iostream>
#include <vector>
#include <algorithm>

class PriorityQueue {
private:
    std::vector<int> heap; // Вектор для хранения элементов кучи

public:
    // Добавление элемента в очередь
    void push(int value) {
        heap.push_back(value);              // Добавляем элемент в конец вектора
        std::push_heap(heap.begin(), heap.end()); // Восстанавливаем свойства кучи
    }

    // Удаление максимального элемента из очереди
    void pop() {
        if (!heap.empty()) {
            std::pop_heap(heap.begin(), heap.end()); // Перемещаем максимальный элемент в конец
            heap.pop_back();                         // Удаляем его из вектора
        }
    }

    // Получение максимального элемента
    int top() const {
        if (!heap.empty()) {
            return heap.front(); // Максимальный элемент всегда находится в начале
        }
        throw std::out_of_range("Queue is empty");
    }

    // Проверка на пустоту
    bool empty() const {
        return heap.empty();
    }

    // Размер очереди
    size_t size() const {
        return heap.size();
    }
};

int main() {
    PriorityQueue pq;

    // Добавляем элементы в очередь
    pq.push(10);
    pq.push(30);
    pq.push(20);
    pq.push(5);

    // Выводим максимальный элемент
    while (!pq.empty()) {
        std::cout << "Max element: " << pq.top() << std::endl;
        pq.pop(); // Удаляем максимальный элемент
    }

    return 0;
}

Объяснение кода:
Куча (Heap) :

Куча — это специальная структура данных, которая позволяет быстро получать максимальный (или минимальный) элемент.
В данном случае мы используем макс-кучу , где максимальный элемент всегда находится в корне (в начале вектора).

Методы :

push: Добавляет элемент в очередь и восстанавливает свойства кучи с помощью std::push_heap.
pop: Удаляет максимальный элемент из очереди. Сначала вызывается std::pop_heap, чтобы переместить максимальный элемент в конец вектора, затем он удаляется с помощью pop_back.
top: Возвращает максимальный элемент (первый элемент вектора).
empty: Проверяет, пуста ли очередь.
size: Возвращает количество элементов в очереди.

Пример работы :

Мы добавляем элементы 10, 30, 20, 5 в очередь.
При каждом вызове top и pop выводится и удаляется максимальный элемент.

Пример вывода:

Max element: 30
Max element: 20
Max element: 10
Max element: 5

Преимущества этого решения:

Простота реализации благодаря использованию стандартных функций.
Эффективность: операции push и pop работают за O(logn), а top — за O(1).