Kinetisk hög

En kinetisk hög är en kinetisk datastruktur som erhålls genom kinetisering av en hög . Den är utformad för att lagra element (nycklar associerade med prioriteringar) där prioriteten ändras som en kontinuerlig funktion av tiden. Som en typ av kinetisk prioritetskö bibehåller den det maximala prioritetselementet lagrat i den. Den kinetiska högdatastrukturen fungerar genom att elementen lagras som ett träd som uppfyller följande heap-egenskap – om $B$ är en barnnod till $A måste$ prioritet för elementet i $A$ vara högre än prioritet för elementet i $B$ . Denna heap-egenskap upprätthålls med hjälp av certifikat längs varje kant så, precis som andra kinetiska datastrukturer, innehåller en kinetisk heap också en prioritetskö (händelsekön) för att upprätthålla certifikatfeltider.

Implementering och drift

En vanlig hög kan kinetiseras genom att utöka med ett certifikat [ $A > B$ ] för varje par av noder A $,$ B $så$ att $B$ är en undernod till $A.$ Om värdet som lagras vid en nod $X$ är en funktion $f X (t)$ av tid, är detta certifikat endast giltigt medan $f A (t) > f B (t)$ . Således måste felet i detta certifikat schemaläggas i händelsekön vid en tidpunkt $t$ så att $f A (t) > fB (t)$ .

Alla certifikatfel är schemalagda på "händelsekön", som antas vara en effektiv prioritetskö vars operationer tar $O(log n)$ tid.

Hantera certifikatfel

När ett certifikat [ $A > B$ ] misslyckas måste datastrukturen byta $A$ och $B$ i högen och uppdatera certifikaten som var och en av dem fanns i.

Till exempel, om $B$ (med undernod $Y$ och $Z$ ) var en undernod till $A$ (med undernod $B$ och $C$ och överordnad nod $X$ ), och certifikatet [ $A > B$ ] misslyckas, måste datastrukturen byta $B$ och $A$ , ersätt sedan de gamla certifikaten (och motsvarande schemalagda händelser) [ $A > B$ ], [ $A < X$ ], [ $A > C$ ], [ $B > Y$ ], [ $B > Z$ ] med nya certifikat [ $B > A$ ], [ $B < X$ ], [ $B > C$ ], [ $A > Y$ ] och [ $A > Z$ ].

Om man antar att händelserna inte degenererar (inga två händelser inträffar samtidigt), behöver endast ett konstant antal händelser av- och omschemaläggas även i värsta fall.

Operationer

En kinetisk hög stöder följande operationer:

$skapa-hög (h)$ : skapa en tom kinetisk hög $h$
$find-max (h, t)$ (eller find-min ): – returnera maxvärdet $($ eller $min$ för en $min-hög$ ) lagrat i högen $h$ vid den aktuella virtuella tiden $t$ .
$infoga (X, f X, t)$ : – infoga en nyckel $X$ i den kinetiska högen vid den aktuella virtuella tiden $t$ , vars värde ändras som en kontinuerlig funktion $f X (t)$ av tiden $t$ . Infogningen görs som i en normal hög i $O(log n)$ -tid, men $O(log n)$ -certifikat kan behöva ändras som ett resultat, så den totala tiden för omschemaläggning av certifikatfel är $O(log 2 n)$
$radera (X, t)$ – radera en tangent $X$ vid den aktuella virtuella tiden $t$ . Borttagningen görs som i en normal heap i $O(log n)$ tid, men $O(log n)$ certifikat kan behöva ändras som ett resultat, så den totala tiden för omschemaläggning av certifikat misslyckanden är $O(log 2 n)$ .

Prestanda

Kinetic heaps presterar bra enligt de fyra mätvärdena ( responsivitet , lokalitet , kompakthet och effektivitet ) för kinetisk datastrukturkvalitet definierad av Basch et al. Analysen av de tre första egenskaperna är enkel:

Lyhördhet : En kinetisk hög är lyhörd, eftersom varje certifikatfel gör att de berörda nycklarna byts ut och leder till att endast ett fåtal certifikat ersätts i värsta fall.
Lokalitet : Varje nod finns i ett certifikat vardera tillsammans med sin överordnade nod och två underordnade noder (om sådana finns), vilket innebär att varje nod kan vara involverad i totalt tre schemalagda händelser i värsta fall, så kinetiska högar är lokala.
Kompakthet : Varje kant i högen motsvarar exakt en schemalagd händelse, därför är antalet schemalagda händelser exakt $n -1$ där $n$ är antalet noder i den kinetiska högen. Således är kinetiska högar kompakta.

Analys av effektivitet

Effektiviteten hos en kinetisk hög i det allmänna fallet är i stort sett okänd. I det speciella fallet med affin rörelse $f(t) = a t + b$ av prioriteringarna är kinetiska högar emellertid kända för att vara mycket effektiva.

Affin rörelse, inga infogningar eller borttagningar

I detta speciella fall kan det maximala antalet händelser som behandlas av en kinetisk hög visas vara exakt antalet kanter i den transitiva stängningen av högens trädstruktur, vilket är $O(n log n)$ för ett träd med höjd $O(log n)$ .

Affin rörelse, med infogningar och borttagningar

Om $n insättningar$ $O(n{\sqrt {n\log n}}).$ raderingar görs på en kinetisk hög som börjar tom, är det maximala antalet bearbetade händelser Denna gräns tros dock inte vara snäv, och den enda kända nedre gränsen är $\Omega ( n\log n)$ .

Varianter

Den här artikeln behandlar "enkla" kinetiska högar som beskrivits ovan, men andra varianter har utvecklats för specialiserade applikationer, som:

Fibonacci kinetisk hög
Inkrementell kinetisk hög

Andra högliknande kinetiska prioritetsköer är:

Guibas, Leonidas. "Kinetiska datastrukturer - Handbok" (PDF) . Arkiverad från originalet (PDF) 2007-04-18 . Hämtad 17 maj 2012 .