Struktura do kolejki priorytetowej ze zmianą priorytetu

Witam.

Mam za zadanie napisać kolejkę priorytetową, coś w formie Schedulera obsługującego zadania na podstawie id i priorytetu, z operacjami dodaj(id, priorytet), usuń, zmień(id, nowy priorytet). Zacząłem realizację tego zadania na kopcu, jednak wyszukiwanie konkretnego id do zmiany priorytetu daje liniowy czas. Myślałem także o RBT + tablica mieszająca w której mapuję id na priorytety przed dodaniem, tak by móc w miarę szybko szukać danego elementu w drzewie. Całość jednak nie wydaję się być zbyt efektowna jak na kolejkę priorytetową. Zna ktoś może sposób, na wydajniejsze zrealizowanie tego zadania?

Podwójne drzewo. Ten sam rekord ma dwie pary lewy, prawy i "siedzi" w dwóch drzewach na raz jedno wg Id drugie wg priorytetu.

Nie widzę żadnej przewagi tego rozwiązania nad wspomnianą przeze mnie wersją - drzewo czerwono-czarne w połączeniu z tablicą mieszającą. Pamięciowo wygląda to tak samo, jednak tablica daje stały dostęp do elementów. Ostatecznie tak to zaimplementowałem. Jeśli się mylę, proszę o poprawienie.