Kupa kinetyczna

Kinetic Heap to kinetyczna struktura danych uzyskana przez kinetyzację sterty . Jest przeznaczony do przechowywania elementów (kluczy związanych z priorytetami), w których priorytet zmienia się w ciągłej funkcji czasu. Jako rodzaj kinetycznej kolejki priorytetowej zachowuje przechowywany w niej element o maksymalnym priorytecie. Struktura danych sterty kinetycznej działa poprzez przechowywanie elementów jako drzewa, które spełnia następującą właściwość sterty — jeśli $B$ jest węzłem potomnym A $,$ to priorytet elementu w $A$ musi być wyższy niż priorytet elementu w $B$ . Ta właściwość sterty jest wymuszana przy użyciu certyfikatów wzdłuż każdej krawędzi, więc podobnie jak inne kinetyczne struktury danych sterta kinetyczna zawiera również kolejkę priorytetową (kolejkę zdarzeń), aby zachować czasy niepowodzenia certyfikatu.

Implementacja i operacje

Zwykła sterta może zostać kinetyzowana poprzez rozszerzenie o certyfikat [ $A > B$ ] dla każdej pary węzłów $A$ , $B ,$ tak że $B$ jest węzłem potomnym $A.$ Jeśli wartość przechowywana w węźle $X$ jest funkcją $f X (t)$ czasu, to ten certyfikat jest ważny tylko wtedy, gdy $f A (t) > f B (t)$ . W związku z tym awaria tego certyfikatu musi zostać zaplanowana w kolejce zdarzeń na czas $t$ taki, że $f A (t) > f B (t)$ .

Wszystkie awarie certyfikatów są planowane w „kolejce zdarzeń”, która z założenia jest wydajną kolejką priorytetową, której operacje zajmują czas $O(log n) .$

Radzenie sobie z błędami certyfikatu

Gdy certyfikat [ $A > B$ ] zawiedzie, struktura danych musi zamienić $A$ i $B$ na stercie i zaktualizować certyfikaty, w których każdy z nich był obecny.

Na przykład, jeśli $B$ (z węzłami podrzędnymi $Y$ i $Z$ ) był węzłem podrzędnym $A$ (z węzłami podrzędnymi $B$ i $C$ i węzłem nadrzędnym $X$ ), a certyfikat [ $A > B$ ] nie powiedzie się, wówczas struktura danych musi zamienić $B$ i $A$ , następnie wymień stare certyfikaty (i odpowiednie zaplanowane zdarzenia) [ $A > B$ ], [ $A < X$ ], [ $A > C$ ], [ $B > Y$ ], [ $B > Z$ ] z nowymi certyfikatami [ $B > A$ ], [ $B < X$ ], [ $B > C$ ], [ $A > Y$ ] i [ $A > Z$ ].

Tak więc, zakładając brak degeneracji wydarzeń (nie ma dwóch wydarzeń w tym samym czasie), tylko stała liczba wydarzeń musi zostać anulowana i ponownie zaplanowana, nawet w najgorszym przypadku.

Operacje

Sterta kinetyczna obsługuje następujące operacje:

$create-heap (h)$ : tworzy pustą stertę kinetyczną $h$
$find-max (h, t)$ (lub find-min ): – zwróć wartość $max$ (lub $min$ dla $min-heap$ ) przechowywaną na stercie $h$ w bieżącym wirtualnym czasie $t$ .
$wstaw (X, f X, t)$ : – wstaw klucz $X$ do sterty kinetycznej w bieżącym czasie wirtualnym $t$ , którego wartość zmienia się jako funkcja ciągła $f X (t)$ czasu $t$ . Wstawianie odbywa się jak w normalnej stercie w $O(log n)$ , ale w rezultacie może zajść potrzeba zmiany certyfikatów $O (log n) , więc całkowity czas na zmianę harmonogramu niepowodzeń certyfikatów wynosi$ $O(log 2 n)$
$delete (X, t)$ – usuń klucz $X$ w bieżącym wirtualnym czasie $t$ . Usuwanie odbywa się jak w normalnej stercie w $O(log n)$ , ale w rezultacie może zajść potrzeba zmiany certyfikatów $O(log n) , więc całkowity czas zmiany harmonogramu niepowodzeń certyfikatów wynosi$ $O(log 2 n)$ .

Wydajność

Sterty kinetyczne działają dobrze zgodnie z czterema metrykami ( responsywność , lokalność , zwartość i wydajność ) jakości kinetycznej struktury danych zdefiniowanych przez Bascha i in. Analiza pierwszych trzech cech jest prosta:

Responsywność : sterta kinetyczna reaguje, ponieważ każdy błąd certyfikatu powoduje zamianę odpowiednich kluczy i prowadzi do zastąpienia tylko kilku certyfikatów w najgorszym przypadku.
Lokalność : każdy węzeł jest obecny w jednym certyfikacie wraz z jego węzłem nadrzędnym i dwoma węzłami podrzędnymi (jeśli istnieją), co oznacza, że każdy węzeł może być zaangażowany w sumie w trzy zaplanowane zdarzenia w najgorszym przypadku, dlatego kopce kinetyczne są lokalne.
Zwartość : każda krawędź w stercie odpowiada dokładnie jednemu zaplanowanemu zdarzeniu, dlatego liczba zaplanowanych zdarzeń wynosi dokładnie $n -1 ,$ gdzie $n$ to liczba węzłów w stercie kinetycznej. Zatem hałdy kinetyczne są zwarte.

Analiza efektywności

Wydajność hałdy kinetycznej w ogólnym przypadku jest w dużej mierze nieznana. Jednak w szczególnym przypadku ruchu afinicznego $f(t) = a t + b$ priorytetów wiadomo, że hałdy kinetyczne są bardzo wydajne.

Ruch afiniczny, bez insercji i usunięć

W tym szczególnym przypadku można wykazać, że maksymalna liczba zdarzeń przetwarzanych przez stertę kinetyczną jest dokładnie równa liczbie krawędzi w przechodnim zamknięciu struktury drzewiastej sterty, czyli $O (n log n)$ dla drzewa wysokości $O(log n)$ .

Ruch afiniczny z insercjami i delecjami

Jeśli $n$ wstawień i usunięć zostanie wykonanych na kopcu kinetycznym, który zaczyna być pusty, maksymalna liczba przetwarzanych zdarzeń wynosi ${\ Displaystyle O (n {\ sqrt {n \ log n}}).}$ Jednak ta granica nie jest uważana za ścisłą, a jedyną znaną dolną granicą jest ${\ Displaystyle \ Omega ( ( n\log n)}$ .

Warianty

Ten artykuł dotyczy „prostych” hałd kinetycznych, jak opisano powyżej, ale opracowano inne warianty do specjalistycznych zastosowań, takie jak:

Kupa kinetyczna Fibonacciego
Przyrostowa sterta kinetyczna

Inne kinetyczne kolejki priorytetowe podobne do sterty to:

Guibas, Leonidas. „Struktury danych kinetycznych - podręcznik” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 18.04.2007 . Źródło 17 maja 2012 r .