W implementacji sterty kolejki priorytetowej ADT element o najwyższej wartości priorytetu zawsze znajduje się w przedniej lub głównej części tablicy?
Czy może jest to miejsce, w którym kolejka priorytetowa ADT o najwyższej wartości priorytetu znajduje się w gnieździe n-1 tablicy?
Odpowiedzi:
1 dla odpowiedzi № 1Sposób zaimplementowania kolejki priorytetowej ma najwyższą wartość zawsze przy pierwszej (zerowej) pozycji tablicy. Zazwyczaj są one implementowane jako sterta:
index 0 1 2 3 4 5 6 7 8 9
parent / 0 0 1 1 2 2 3 3 4
Dzieje się tak, ponieważ rodzic jest łatwo odnajdywany przez
(index - 1) / 2
(gdy używany jest podział całkowity)
1 dla odpowiedzi nr 2
Możesz zanegować priorytet i uzyskać to, co chcesz.
Nie jest jednak poprawnie mówić o gnieździe n-1, ponieważ jest to szczegóły implementacji (w tym przypadku w C ++) std::priority_queue szablon klasy. I już nie chodzi o ADT, ale szczegóły implementacji.
Właściwie możesz go użyć do swoich celów: Na przykład. zwykła kolejka priorytetowa dla int std::priority_queue<int>, ale z przeciwnymi priorytetami jest std::priority_queue<int, std::vector<int>, std::greater<int> >