Tråkigt

En Queap Q med k = 6 och n = 9

Inom datavetenskap är en queap en prioriterad ködatastruktur . Datastrukturen tillåter infogning och borttagning av godtyckliga element, samt hämtning av det högst prioriterade elementet. Varje radering tar amorterad tidslogaritmisk i antalet objekt som har funnits i strukturen under en längre tid än det borttagna objektet. Insättningar tar konstant amorterad tid.

Datastrukturen består av en dubbellänkad lista och en 2–4 träddatastruktur , var och en modifierad för att hålla reda på dess minsta prioritetselement. Den grundläggande operationen för strukturen är att behålla nyinfogade element i den dubbellänkade listan, tills en radering skulle ta bort ett av listobjekten, vid vilken tidpunkt de alla flyttas in i 2–4-trädet. Trädet 2–4 lagrar dess element i infogningsordning, snarare än den mer konventionella prioritetssorterade ordningen.

Både datastrukturen och dess namn har tagits fram av John Iacono och Stefan Langerman .

Beskrivning

En queap är en prioriterad kö som infogar element i O (1) amorterad tid, och tar bort minimielementet i O (log( k + 2)) om det finns k objekt som har funnits i högen under en längre tid än elementet som ska utvinnas. queapen har en egenskap som kallas egenskapen queueish: tiden för att söka efter element x är O(lg q ( x )) där q ( x ) är lika med n − 1 − w ( x ) och w ( x ) är talet av distinkta objekt som har nåtts genom operationer som sökning, infogning eller borttagning. q ( x ) definieras som hur många element som inte har nåtts sedan x :s senaste åtkomst. Egenskapen queueish är faktiskt komplementet till egenskapen splay tree working set: tiden för att söka efter element x är O (lg w ( x )).

En queap kan representeras av två datastrukturer: en dubbellänkad lista och en modifierad version av 2–4-trädet. Den dubbellänkade listan, L , används för en serie infognings- och lokaliserings-min-operationer. Den queap håller en pekare till det minsta elementet lagrat i listan. För att lägga till element x till lista l läggs elementet x till i slutet av listan och en bitvariabel i element x sätts till ett. Denna operation görs för att avgöra om elementet antingen finns i listan eller i ett 2–4-träd.

Ett 2–4-träd används när en raderingsoperation inträffar. Om objektet x redan finns i träd T tas objektet bort med 2–4-trädets raderingsoperation. Annars finns objektet x i lista L (görs genom att kontrollera om bitvariabeln är satt). Alla element som är lagrade i lista L läggs sedan till i 2–4-trädet, vilket sätter bitvariabeln för varje element till noll. x tas sedan bort från T .

En queap använder endast 2–4 trädstrukturegenskaperna, inte ett sökträd. Den modifierade 2–4 trädstrukturen är som följer. Anta att listan L har följande uppsättning element: $x_{1},x_{2},x_{3},\dots ,x_{k}$ . När raderingsoperationen anropas, läggs uppsättningen av element lagrade i L sedan till bladen på 2–4-trädet i den ordningen, fortlöpande av ett dummyblad som innehåller en oändlig nyckel. Varje intern nod i T har en pekare ${\displaystyle h_{v}} ,$ som pekar på det minsta objektet i underträdet v . Varje intern nod på väg P från roten till $x_{0}$ har en pekare ${\displaystyle c_{v}} ,$ som pekar på den minsta nyckeln i ${\ displaystyle T-T_{v}-\{r\}}$ . h ${\displaystyle h_{v}}-$ för varje intern nod på väg P ignoreras. Queapen har en pekare till ${\displaystyle c_{x_{0}}} ,$ som pekar på det minsta elementet i T .

En applikation av queaps inkluderar en unik uppsättning av högprioriterade händelser och extraktion av den högst prioriterade händelsen för bearbetning.

Operationer

Låt minL vara en pekare som pekar på minimielementet i den dubbellänkade listan L , $c_{x_{0}}$ är minimielementet lagrat i 2–4-trädet, T , k är antalet av element lagrade i T , och n är det totala antalet element lagrade i queap Q . Operationerna är som följer:

New(Q): Initierar en ny tom queap.

Initiera en tom dubbellänkad lista L och 2–4 träd T . Sätt k och n till noll.

Infoga (Q, x): Lägg till elementet x till queap Q .

Infoga elementet x i lista L . Sätt biten i element x till ett för att visa att elementet finns i listan L . Uppdatera minL- pekaren om x är det minsta elementet i listan. Öka n med 1.

Minimum(Q): Hämta en pekare till det minsta elementet från queap Q .

Om nyckel(minL) < nyckel (

c_{x_{0}}

), returnera minL . Annars returnerar du

c_{x_{0}}

.

Ta bort(Q, x): Ta bort element x från queap Q .

Om biten av elementet x är satt till ett, lagras elementet i listan L . Lägg till alla element från L till T , ställ in biten för varje element till noll. Varje element läggs till föräldern till det högra barnet av T med hjälp av infogningsoperationen i 2–4-trädet. L blir tom. Uppdatera

h_{v}

pekare för alla noder v vars barn är nya/modifierade, och upprepa processen med nästa förälder tills föräldern är lika med roten. Gå från roten till noden

x_{0}

och uppdatera

{\displaystyle c_{v}}-

värdena. Sätt k lika med n .

Om biten av elementet x är noll, är x ett blad av T . Ta bort x med 2–4-trädets raderingsoperation. Börja från nod x , gå in i T till nod

x_{0}

, uppdatera

h_{v}

och

c_{v}

pekare. Minska n och k med 1.

DeleteMin(Q): Ta bort och returnera det minsta elementet från queap Q .

Anropa Minimum(Q) -operationen. Operationen returnerar min . Anropa åtgärden Delete(Q, min) . Retur min .

CleanUp(Q): Ta bort alla element i lista L och träd T .

Börja från det första elementet i lista L , gå igenom listan och ta bort varje nod.

Börja från roten av trädet T , gå igenom trädet med hjälp av post-order-traversalalgoritmen , ta bort varje nod i trädet.

Analys

Löptiden analyseras med den amortiserade analysen . Potentialfunktionen för queap Q kommer att vara $\phi (Q)=c|L|$ där $Q=(T,L)$ .

Infoga(Q, x): Kostnaden för operationen är O(1) . Storleken på lista L växer med ett, potentialen ökar med någon konstant c .

Minimum(Q): Operationen ändrar inte datastrukturen så den amorterade kostnaden är lika med dess faktiska kostnad, O(1).

Ta bort(Q, x): Det finns två fall.

Fall 1

Om x är i trädet T ändras inte den upplupna kostnaden. Raderingsoperationen är O(1) amorterad 2–4 träd. Eftersom x togs bort från trädet kan $h_{v}$ och ${\displaystyle c_{v}}-$ pekarna behöva uppdateras. Som mest kommer det att finnas ${\displaystyle O(lgq(x))}-$ uppdateringar.

Fall 2

Om x finns i lista L så infogas alla element från L i T . Detta har en kostnad av $a|L|$ av någon konstant a , avskriven över 2–4-trädet. Efter att ha infogat och uppdaterat $h_{v}$ och ${\displaystyle c_{v}}-$ pekarna, begränsas den totala tiden som spenderas av $2a|L|$ . Den andra operationen är att ta bort x från T och att gå på vägen från x till ${\displaystyle x_{0}},$ korrigera $h_{v}$ och $c_{v}$ värden. Tiden går åt högst $2a|L|+O(lgq(x))$ . Om $c>2a$ kommer den upplupna kostnaden att vara $O(lgq(x))$ . Delete(Q, x): är tillägget av den amorterade kostnaden för Minimum(Q) och Delete(Q, x) , vilket är $O(lgq(x))$ .

Kodexempel

En liten Java- implementering av en queap:

  

       
       
           
      

      
          0
          0
           
           
    

        
          
    

           
           0
              
        
          
           0
              
    

         
        
           0
             

         
    

           
        
        
        
    

           
         
          
            
               
              
             
        
              
             
    

         
           
         
         
    
 public  class  Queap  {  public  int  n  ,  k  ;  offentlig  lista  <  Element  >  l  ;  // Element är en generisk datatyp.  offentliga  QueapTree  t  ;  // ett 2-4-träd, modifierat för Queap-ändamål  public  Element  minL  ;  privat  Queap  ()  {  n  =  ;  k  =  ;  l  =  new  LinkedList  <  Element  >  ();  t  =  new  QueapTree  ();  }  public  static  Queap  New  ()  {  return  new  Queap  ();  }  public  static  void  Infoga  (  Queap  Q  ,  Element  x  )  {  if  (  Q  .  n  ==  )  Q  .  minL  =  x  ;  Q  .  l  .  lägg till  (  x  );  x  .  inList  =  sant  ;  if  (  x  .  compareTo  (  Q  .  minL  )  <  )  Q  .  minL  =  x  ;  }  public  static  Element  Minimum  (  Queap  Q  )  {  // t är ett 2-4-träd och x0, cv är trädnoder.  if  (  Q.  minL  .  compareTo  (  Q.  t  .  x0  .  cv  .  key  )  <  )  returnera  Q.  _  _  _  minL  ;  returnera  Q.  _  t  .  x0  .  cv  .  nyckel  ;  }  public  static  void  Delete  (  Queap  Q  ,  QueapNode  x  )  {  Q  .  t  .  deleteLeaf  (  x  );  --  Q  .  n  ;  --  Q  .  k  ;  }  public  static  void  Delete  (  Queap  Q  ,  Element  x  )  {  QueapNode  n  ;  if  (  x  .  inList  )  {  //  sätt inList av alla element i listan till false  n  =  Q.  t  .  insertList  (  Q.l  ,  x  )  ;  _  Q  .  k  =  Q.  _  n  ;  Ta bort  (  Q  ,  n  );  }  else  if  ((  n  =  Q  .  t  .  x0  .  cv  ).  nyckel  ==  x  )  Ta bort  (  Q  ,  n  );  }  public  static  Element  DeleteMin  (  Queap  Q  )  {  Element  min  =  Minimum  (  Q  );  Ta bort  (  Q  ,  min  );  retur  min  ;  }  }

Se även