Kiedy należy użyć make_heap vs. Priority Queue?

Question

Mam wektor, którego chcę użyć do utworzenia sterty. Nie jestem pewien, czy powinienem użyć funkcji make_heap C++ lub umieścić mój wektor w kolejce priorytetowej? Co jest lepsze pod względem wydajności? Kiedy powinienem użyć jednego z drugim?

Answer 1

Nie ma różnicy w zakresie wydajności. std::priority_queue to tylko klasa adaptera, która opakowuje kontener i identyczne wywołania funkcji związanych z stertami w klasie. Specyfikacja std::priority_queue otwarcie stwierdza, że.

Budując kolejkę priorytetową opartą na sterty z odsłoniętego std::vector (bezpośrednio wywołując funkcje związane z stertami), pozostaje ona otwarta na możliwość dostępu z zewnątrz, potencjalnie uszkadzając integralność sterty/kolejki. std::priority_queue działa jako bariera ograniczająca dostęp do minimum "kanonicznego": push(), pop(), top() itd. Możesz to zobaczyć jako środek wymuszający samodyscyplinę.

Ponadto, dostosowując interfejs kolejki do "kanonicznego" zestawu operacji, czynisz go jednolitym i wymiennym z innymi wersjami kolejek priorytetów zgodnych z tą samą specyfikacją zewnętrzną.

Answer 2

Parametr priority_queue jest (co najmniej normalnie) implementowany jako sterty. W związku z tym prawdziwe pytanie brzmi, czy parametr priority_queue zapewnia to, czego potrzebujesz. Kiedy używasz make_heap, nadal masz dostęp do wszystkich elementów. Kiedy używasz parametru priority_queue, masz tylko kilka operacji, które dają bardzo ograniczony dostęp do elementów (w zasadzie wystarczy wstawić element i usunąć element na początku kolejki).

Answer 3

priority_queue nie jest kontenerem. Jest to adapter kontenera, który używa określonego bazowego kontenera, np. vector lub deque i zapewnia określony zestaw metod pracy z danymi. Co więcej, jego implementacja opiera się na algorytmach *_heap.

Na przykład za każdym razem, gdy naciskasz nową wartość na vector, powinieneś zadzwonić pod numer push_heap, aby rozszerzyć zakres uważany za stertę. Jeśli nie używasz priority_queue, możesz rozważyć, powiedzmy, połowę vector jako stertę (std::make_heap(v.begin(), v.begin() + (v.size()/2))), podczas gdy druga połowa będzie taka, jaka jest.

priority_queue Co robi podczas rozmowy push na nim: on popycha nowy element do tyłu bazowego pojemnika i wzywa push_heap zachować właściwości sterty priorytet (ma to znaczenie tylko pierwszy element będzie największa).

Powiedziałbym, że lepiej rozważyć projekt rozwiązania i konkretne wymagania, a nie problemy z wydajnością.

Answer 4

Jeśli nie chcesz modyfikować tego wektora, powinieneś użyć kolejki priorytetowej, ponieważ tworzy on oddzielny wektor (wymaga dodatkowej przestrzeni). Co więcej, jest łatwy do wdrożenia. Na przykład, gdy używasz make_heap podczas poppingu elementu, musisz użyć dwóch poleceń, najpierw pop_heap, a następnie pop_back ... ale możesz to zrobić za pomocą tylko jednego polecenia w przypadku kolejki priorytetowej. Podobnie, wpychając element do sterty.
Teraz wydajność obu będzie taka sama, ponieważ kolejka priorytetowa nie jest kontenerem i używa jakiegoś bazowego kontenera jako wektora lub deque, który używa takich samych operacji sterty, jak używane przez operacje make_heap. Więc powinieneś użyć jednego w zależności od twoich wymagań .