Kinetisk värmare

En kinetisk värmare är en kinetisk prioritetskö som liknar en kinetisk hög , som använder randomisering för att förenkla analysen på ett sätt som liknar en treap . Specifikt har varje element en slumpmässig nyckel associerad med sig utöver dess prioritet (som ändras som en kontinuerlig funktion av tiden som i alla kinetiska datastrukturer ). Den kinetiska värmaren är då samtidigt ett binärt sökträd på elementnycklarna och en hög på elementprioriteterna. Den kinetiska värmaren uppnår (förväntade) asymptotiska prestandagränser lika med de bästa kinetiska prioritetsköerna. I praktiken är det dock mindre effektivt eftersom de extra slumpmässiga nycklarna måste lagras, och proceduren för att hantera certifikatfel är en (relativt komplicerad) rotation istället för ett enkelt byte.

Genomförande

Om varje element har en nyckel och en prioritet kopplad till den, så finns det en unik trädstruktur som samtidigt är ett sökträd på nycklarna och en hög på prioriteringarna - denna struktur motsvarar treapen (om prioriteringarna är slumpmässigt valda) eller den kinetiska värmaren (om nycklarna är slumpmässigt valda).

Giltigheten av trädstrukturen säkerställs genom att skapa ett certifikat vid varje kant som upprätthåller heap-egenskapen på den kanten. Den huvudsakliga operativa skillnaden mellan en kinetisk hög och en kinetisk värmare är hur de reagerar på certifikatfel. När ett certifikat på en kant misslyckas, kommer en kinetisk värmare att utföra en rotation runt noderna som misslyckades (istället för bytet som en kinetisk hög skulle utföra).

Betrakta till exempel elementen B (med förälder F ) och dess vänstra underordnade D (med högra underordnade C ). När certifikatet [ B > D ] på kanten BD misslyckas, kommer trädet att roteras runt denna kant. Så i detta fall har den resulterande strukturen D i stället för B , C blir ett underordnat av B istället för D , och det finns tre certifikatändringar [B>D] ersatt med [D>B], [D>C] ersatt med [B>C] och [F>B] ersatts med [F>D]. Allt annat förblir detsamma.

Analys

Denna kinetiska datastruktur är:

• Responsive : Det finns O(1) certifikatuppdateringar som måste göras när ett certifikat misslyckas, vilket tar O(log n) tid
• Lokalt : Varje element är involverat i O(1)-certifikat
• Kompakt : Det finns O(n) totala certifikat
• Effektiv : Den har samma (förväntade) asymptotiska prestanda som kinetic hanger , kinetic tournament - för en samling av rymd-tidsbanor där varje par skär högst s gånger, den kinetiska värmaren bearbetar O(λ _s+2 log n ) händelser i . O(As ₊₂ ^log2n ) tid , där Xs ₊₂ är en Davenport-Schinzel - sekvens

Basch, J. "Kinetic Data Structures" . Hämtad 17 maj 2012 .