priority_queue ma'lumotlar tuzilmasi nima?

priority_queue — C++ standarta kutubxonasidan konteyner adaptori bo‘lib, ustunlik navbatining funksiyasini taqdim etadi. Elementlar ustunlik bo‘yicha chiqariladi (standart holatda, eng katta element eng yuqori ustunlikka ega). Asosan, bu boshqa konteyner (standart holatda std::vector) ustiga qoplangan bo‘lib, std::make_heap, std::push_heap, std::pop_heap algoritmlari yordamida asosiy konteyner ichida yigin tuzilmasini saqlaydi.

Asosiy xususiyatlar:

• Ustunlik: Elementlar ularning ustunligiga ko‘ra chiqariladi. Standart holatda, std::less ishlatiladi, bu eng katta element eng yuqori ustunlikka ega bo‘lishini anglatadi (maksimal yigin). Tartibni o‘zgartirish uchun boshqa solishtiruvchini, masalan, std::greater ni taqdim etish mumkin.
• Adaptori: priority_queue mustaqil konteyner emas, balki boshqa asosiy konteynerga (odatda std::vector, lekin std::deque ham bo‘lishi mumkin) moslashtirilgan va ustunlik navbati interfeysini taqdim etadi.
• Yigin: Ichki ravishda yigin yordamida amalga oshirilgan, bu qo‘shish va chiqarish operatsiyalarining logarifmik murakkabligini ta’minlaydi.
• Noto‘g‘ri kirish: Elementlarga tasodifiy kirishni ta’minlamaydi. Faqat qo‘shish (push), eng yuqori ustunlikdagi elementni chiqarish (pop) va eng yuqori ustunlikdagi elementga qarash (top) operatsiyalari mavjud.

Asosiy operatsiyalar:

Operatsiya	Tavsifi	Murakkablik (o‘rtacha/eng yomon holatda)
push	Belgilangan ustunlik bilan element qo‘shadi.	O(log N)
pop	Eng yuqori ustunlikdagi elementni olib tashlaydi.	O(log N)
top	Eng yuqori ustunlikdagi elementga doimiy havola qaytaradi.	O(1)
empty	Navbat bo‘sh yoki yo‘qligini tekshiradi.	O(1)
size	Navbatdagi elementlar sonini oladi.	O(1)

Misol:

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // std::greater uchun

int main() {
    // Maksimal yigin (standart)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Maksimal yigin elementlari (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Minimal yigin (std::greater<int> yordamida)
    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 << "Minimal yigin elementlari (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}