Wieszak kinetyczny

Wieszak kinetyczny to losowa wersja stosu kinetycznego , którego działanie można łatwo dokładnie przeanalizować. Wieszak kinetyczny spełnia właściwość sterty (priorytet każdego elementu jest wyższy niż priorytet jego elementów podrzędnych), ale łagodzi wymóg ścisłej równowagi struktury drzewa, dzięki czemu wstawienia i usunięcia mogą być losowe. W rezultacie struktura wieszaka kinetycznego ma tę właściwość, że jest rysowana jednostajnie losowo z przestrzeni wszystkich możliwych struktur hałdowych na swoich elementach.

Realizacja

Struktura wieszaka kinetycznego (w tym certyfikaty i kolejka zdarzeń) jest dokładnie taka sama jak struktura sterty kinetycznej, ale bez wymogu równoważenia. Składa się zatem z wydajnej kolejki priorytetowej (kolejki zdarzeń) do utrzymywania czasów awarii certyfikatu, a także głównej (niekoniecznie zrównoważonej) struktury drzewiastej przypominającej stertę , w której przechowywane są elementy. Z każdą krawędzią powiązany jest certyfikat, który wymusza właściwość sterty (priorytet elementu nadrzędnego > priorytet elementu podrzędnego) wzdłuż tej krawędzi.

Charakterystyczną operacją w wieszaku kinetycznym jest „ wiszenie ”, które definiuje się w następujący sposób (rozróżnia się węzeł w strukturze drzewa i przechowywany w nim element). Zawieś(węzeł n, element e)

1. Jeśli nie ma elementu w n , wstaw e w n i wróć
2. Jeśli element x w n ma wyższy priorytet niż e , wybierz losowo dziecko c z n i wywołaj rekurencyjnie Hang(c, e)
3. Jeśli element x w n ma niższy priorytet niż e , umieść e w n wybierz losowo i rekurencyjnie dziecko c z n Wywołaj Hang(c, x)

Główna różnica między wieszakiem kinetycznym a hałdą kinetyczną polega na kluczowych operacjach, które są realizowane w następujący sposób w wieszaku kinetycznym:

• Build-hanger: najpierw posortuj elementy według priorytetu, a następnie wywołaj zawieszenie w katalogu głównym dla każdego elementu w kolejności. Następnie oblicz i zaplanuj czasy awarii certyfikatów w kolejce zdarzeń. Zajmuje to czas O(n log n), podobnie jak sterta kinetyczna.
• Wstaw: Wieszak kinetyczny wstawia od góry do dołu (zamiast od dołu do góry), „ zawieszając ” nowy element w węźle głównym. Zajmuje to czas O(log n), ale certyfikaty O(log n) mogą wymagać zmiany w drodze w dół, więc całkowity czas wynosi O (log ² n )
• Usuń: Jest to prostsza operacja niż w przypadku sterty, ponieważ równoważenie struktury drzewa nie musi być utrzymywane. W ten sposób element jest po prostu zastępowany większym z jego dzieci, a następnie to dziecko jest rekurencyjnie usuwane. Ponownie zajmuje to O(log n) czasu, ale certyfikaty O(log n) mogą wymagać aktualizacji, więc całkowity czas to O (log ² n ) .

Wszystkie te operacje skutkują jednakowo losową strukturą wieszaka o oczekiwanej wysokości O(log n).

Analiza

Ta struktura to:

• Responsive : przetwarzanie błędu certyfikatu zajmuje czas O (log n), podobnie jak w stercie kinetycznej
• Lokalny : każdy element jest zaangażowany w certyfikaty O(1), podobnie jak w stercie kinetycznej
• Kompaktowy: istnieje łącznie certyfikatów O(n), podobnie jak w stercie kinetycznej
• Wydajny : ma taką samą wydajność jak turniej kinetyczny lub grzejnik kinetyczny - dla zbioru trajektorii czasoprzestrzennych, w których każda para przecina się co najwyżej s razy, wieszak kinetyczny przetwarza zdarzenia O(λ _{s +2} log n ) w O(λ _{s +2} log ² n ) czas, gdzie λ _{s +2} to ciąg Davenporta-Schinzela

da Fonseca, Guilherme D. i de Figueiredo, Celina MH i Carvalho, Paulo CP „Kinetic wieszak” (PDF) . Listy dotyczące przetwarzania informacji. s. 151–157. Zarchiwizowane od oryginału (PDF) w dniu 24 maja 2015 r . Źródło 17 maja 2012 r . {{ cite web }} : CS1 maint: wiele nazw: lista autorów ( link )