сохтори додаи priority_queue чист?

priority_queue — адаптер контейнера аз китобхонаи стандартии C++, ки функсионалиятрои навъи навбат бо афзалиятҳоро таъмин мекунад. Элементҳо мувофиқи афзалияташон бароварда мешаванд (аз пеш, унсури баландтарин дорои афзалияти баландтар аст). Дар асл, ин як пӯшида бар рӯи дигар контейнер (аз пеш std::vector) аст, ки алгоритмҳои heap (std::make_heap, std::push_heap, std::pop_heap) барои нигоҳ доштани сохтори heap дар дохили контейнери асосӣ истифода мешавад.

Хусусиятҳои асосӣ:

• Афзалият: Элементҳо мувофиқи афзалияташон бароварда мешаванд. Аз пешгузашта, std::less истифода мешавад, ки маънои онро дорад, ки унсури бузургтарин бо афзалияти баландтар ҳисобида мешавад (max-heap). Рӯйхати дигаре, масалан, std::greater, барои min-heap, пешниҳод кардан мумкин аст.
• Адаптер: priority_queue контейнер мустақил нест, балки дигар контейнер (одатан std::vector, аммо метавонад std::deque бошад) -ро адапт мекунад ва интерфейси навъи навбат бо афзалиятҳоро пешниҳод мекунад.
• Heap: Дар дохили он бо истифода аз heap амалӣ шудааст, ки мураккабии логарифмиро барои амалҳои ворид кардан ва баровардан таъмин мекунад.
• Дастрасии беинтихоб: Дастрасӣ ба унсурҳо ба таври тасодуфӣ нест. Фақат амалҳои ворид кардан (push), баровардани унсури бо афзалияти баландтарин (pop) ва тамошо кардани унсури бо афзалияти баландтарин (top) дастрасанд.

Амалиётҳои асосӣ:

Амалия	Тавсиф	Мураккабии (дар миёна/бадтарин ҳолат)
push	Ворид кардани унсур бо афзалияти муайян.	O(log N)
pop	Баровардани унсури бо афзалияти баландтарин.	O(log N)
top	Баргардонидани истинод констант ба унсури бо афзалияти баландтарин.	O(1)
empty	Санҷидани холии навъи навбат.	O(1)
size	Гирифтани шумораи унсурҳо дар навъи навбат.	O(1)

Маслиҳат барои истифода:

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // барои std::greater

int main() {
    // Max-heap (аз пешгузашта)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Элементҳои max-heap (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Min-heap (бо истифода аз std::greater<int>)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);

    std::cout << "Элементҳои min-heap (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Дар алгоритмҳо истифода мешавад, ки дар он ҷо лозим аст, ки пайваста унсури бо баландтарин (ё пасттарин) афзалиятро бароварда, интихоб кунанд, масалан, алгоритми Дейкстра, алгоритми Прим ё дар моделсозии ҳодисаҳо.