Mam priorytetową kolejkę zdarzeń, ale czasami priorytety zdarzeń zmieniają się, dlatego chciałbym przechowywać iteratory od requesterów zdarzeń do sterty. Jeśli priorytet się zmieni, chciałbym, żeby sterta została skorygowana w log (n) czasie. Zawsze będę miał dokładnie jeden iterator wskazujący na każdy element w stercie.Czy istnieje klasa sterty w C++, która obsługuje zmianę priorytetu elementów innych niż głowa?
Cieszę się zgłosić, które zwiększają dodano teraz Boost.Heap library z niektórymi stellar data structures.
Zaletą tego jest fakt, że kupony Fibonacciego zmieniają priorytet w stałym amortyzowanym czasie.
Niestety, wszystkie zmienne stosy są oparte na węzłach (innymi słowy, mają dodatkowe pośrednie zgodnie z sugestią @wilx). Odpowiedź @ Feruccia na "zmienne stosy Boosta" ma kod, który pozwala pisać zmienne stosy oparte na wektorach, jeśli chcesz mieć wskaźniki do uchwytów zawartych w twoim typie wartości.
To brzmi, jakbyś potrzebował więcej pośrednictwa. Zamiast tego zapisz wskaźnik do zdarzeń w kolejce priorytetów. Gdy priorytet zmieni się w elemencie kolejki, usuń go i włóż ponownie.
Spójrz na Boost's mutable heaps.
ostrzeżenie jest to, że możesz skończyć z niestabilnym przypadku sortowania, czyli kolejność wydarzeń z takim samym priorytetem jest niezdefiniowany (read „zostaną zreorganizowane”).
Możesz usunąć dowolny element ze sterty w czasie log (n). –
Tak, masz rację, myślałeś o czymś innym :) –
nie ma problemu :) –
Dzięki, jeśli będę musiał przetaczać własne, użyję tego fragmentu, by zacząć. –
skończyło się na tym rozwiązaniu –
@Ferruccio Dzięki, zaoszczędziło mi dobre 45 minut i kilka błędów. –