std::priority queue (tsz. std::priority queues)

1. (informatika)

A prioritásos sor (priority_queue) egy speciális adattípus, amely hasonló egy normál sorhoz (queue), de az elemek prioritás szerint kerülnek feldolgozásra.

• Alapértelmezés szerint a legnagyobb elem van elöl (max heap).
• O(log N) beszúrás és törlés a háttérben egy heap (kupac) adatszerkezettel.
• Rendezett tárolás nélkül biztosítja a legnagyobb vagy legkisebb elem gyors elérését.

A priority_queue alapértelmezett viselkedése egy max heap, vagyis mindig a legnagyobb elem lesz a tetején (top()).

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    // Elembeszúrás
    pq.push(10);
    pq.push(30);
    pq.push(20);
    pq.push(5);

    // Kiírás a legnagyobb elemek szerint
    std::cout << "Prioritásos sor elemei (csökkenő sorrendben): ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

Prioritásos sor elemei (csökkenő sorrendben): 30 20 10 5

🔹 Magyarázat:
- A push() függvény beszúr egy elemet O(log N) időben. - A top() mindig a legnagyobb elemet adja vissza O(1) időben. - A pop() eltávolítja a legnagyobb elemet O(log N) időben.

Ha azt szeretnénk, hogy a legkisebb elem legyen elöl (min heap), akkor használhatjuk a greater<int> komparátort.

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

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    pq.push(10);
    pq.push(30);
    pq.push(20);
    pq.push(5);

    std::cout << "Prioritásos sor elemei (növekvő sorrendben): ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

Prioritásos sor elemei (növekvő sorrendben): 5 10 20 30

🔹 Magyarázat: - A std::greater<int> komparátorral min heap-et hozunk létre. - A top() mindig a legkisebb elemet adja vissza.

Ha egy saját struktúrát vagy osztályt szeretnénk prioritás szerint tárolni, akkor egyedi komparátort kell megadnunk.

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

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

    // Egyedi összehasonlító operátor (min heap)
    bool operator>(const Task& other) const {
        return priority > other.priority; // Min heap: kisebb prioritás előbb jön
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, std::greater<Task>> pq;

    pq.push({3, "Takarítás"});
    pq.push({1, "Bevásárlás"});
    pq.push({2, "Programozás"});
    pq.push({4, "Edzés"});

    std::cout << "Feladatok prioritás szerint: " << std::endl;
    while (!pq.empty()) {
        std::cout << "Prioritás: " << pq.top().priority << " - " << pq.top().name << std::endl;
        pq.pop();
    }

    return 0;
}

Feladatok prioritás szerint:
Prioritás: 1 - Bevásárlás
Prioritás: 2 - Programozás
Prioritás: 3 - Takarítás
Prioritás: 4 - Edzés

🔹 Magyarázat: - Egy Task struktúra tartalmaz egy prioritást és egy nevet. - A operator> segítségével min heap-et hozunk létre. - A legkisebb prioritású feladat kerül először végrehajtásra.

Ha egyedi prioritási szabályokat akarunk megadni, használhatunk külső komparátort.

#include <iostream>
#include <queue>

struct Compare {
    bool operator()(int a, int b) {
        return a % 10 > b % 10; // Az utolsó számjegy szerint prioritizálunk
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, Compare> pq;

    pq.push(21);
    pq.push(35);
    pq.push(42);
    pq.push(17);

    std::cout << "Elemsorrend prioritás szerint: ";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

Elemsorrend prioritás szerint: 42 21 35 17

🔹 Magyarázat: - Az utolsó számjegy szerint priorizálunk (mod 10 érték). - A legkisebb utolsó számjegyű elem kerül előre.

✅ A priority_queue egy hatékony adatszerkezet, amely lehetővé teszi a legnagyobb vagy legkisebb elem gyors elérését.
✅ Alapértelmezés szerint max heap (std::priority_queue<int>).
✅ Min heap-hez használható a std::greater<int> vagy egyedi komparátor.
✅ Egyedi osztályok és struktúrák is kezelhetők egyedi komparátorokkal.
✅ Hatékony: O(log N) beszúrás és törlés, O(1) a legfontosabb elem elérése.

• std::priority queue - Szótár.net (en-hu)
• std::priority queue - Sztaki (en-hu)
• std::priority queue - Merriam–Webster
• std::priority queue - Cambridge
• std::priority queue - WordNet
• std::priority queue - Яндекс (en-ru)
• std::priority queue - Google (en-hu)
• std::priority queue - Wikidata
• std::priority queue - Wikipédia (angol)