Skev hög

En skew heap (eller självjusterande heap ) är en heap- datastruktur implementerad som ett binärt träd . Skew heaps är fördelaktiga på grund av deras förmåga att smälta samman snabbare än binära heaps. I motsats till binära högar finns det inga strukturella begränsningar, så det finns ingen garanti för att trädets höjd är logaritmisk. Endast två villkor måste vara uppfyllda:

Den allmänna heapordern måste verkställas
Varje operation (add, remove_min, merge) på två skew heaps måste göras med en speciell skew heap merge .

En skevhög är en självjusterande form av en vänsterhög som försöker upprätthålla balans genom att ovillkorligen byta alla noder i sammanfogningsvägen när två högar slås samman. (Merge-operationen används också när man lägger till och tar bort värden.) Utan några strukturella begränsningar kan det tyckas som om en skevhög skulle vara fruktansvärt ineffektiv. Emellertid amortiserad komplexitetsanalys användas för att visa att alla operationer på en skew heap kan göras i O(log n ). Faktum är att med ${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ som anger det gyllene snittet , är den exakta amorterade komplexiteten känd för att vara log _φ n (ungefär 1,44 log2n ₎ .

Definition

Skew heaps kan beskrivas med följande rekursiva definition: ^{[ citat behövs ]}

En hög med bara ett element är en skev hög.
Resultatet av att skeva sammanslagning av två skevhögar $sh_{1}$ och $sh_{2}$ är också en skevningshög.

Operationer

Slår ihop två högar

När två skevhögar ska slås samman kan vi använda en liknande process som sammanslagning av två vänsterhögar :

Jämför rötter av två högar; låt p vara högen med den mindre roten och q vara den andra högen. Låt r vara namnet på den resulterande nya högen.
Låt roten till r vara roten till p (den mindre roten), och låt r:s högra underträd vara p:s vänstra underträd.
Beräkna nu r:s vänstra underträd genom att rekursivt slå samman p:s högra underträd med q.

   
     

       
       

       
         

        
         

      
    
           
          
           
         
    
    
          
 mall  <  class  T  ,  class  CompareFunction  >  SkewNode  <  T  >*  CSkewHeap  <  T  ,  CompareFunction  >::  _Merge  (  SkewNode  <  T  >*  root_1  ,  SkewNode  <  T  >*  root_2  )  {  SkewNode  <  T  >*  firstRoot  =  root_1  ;  SkewNode  <  T  >*  secondRoot  =  root_2  ;  if  (  firstRoot  ==  NULL  )  returnera  secondRoot  ;  annars  if  (  secondRoot  ==  NULL  )  returnerar  firstRoot  ;  if  (  sh_compare  ->  Less  (  firstRoot  ->  key  ,  secondRoot  ->  key  ))  {  SkewNode  <  T  >*  tempHeap  =  firstRoot  ->  rightNode  ;  firstRoot  ->  rightNode  =  firstRoot  ->  leftNode  ;  firstRoot  ->  leftNode  =  _Merge  (  secondRoot  ,  tempHeap  );  returnera  firstRoot  ;  }  annars  returnerar  _Merge  (  secondRoot  ,  firstRoot  );  }

Innan:

efter

Icke-rekursiv sammanslagning

Alternativt finns det ett icke-rekursivt tillvägagångssätt som är mer ordrikt och som kräver viss sortering i början.

Dela upp varje hög i underträd genom att skära av varje väg. (Från rotnoden, skär av den högra noden och gör det högra barnet till ett eget underträd.) Detta kommer att resultera i en uppsättning träd där roten antingen bara har ett vänsterbarn eller inga barn alls.
Sortera underträden i stigande ordning baserat på värdet på rotnoden för varje underträd.
Medan det fortfarande finns flera underträd, rekombinera iterativt de två sista (från höger till vänster).
- Om roten till det näst sista underträdet har ett vänster underordnat, byt ut det till det högra underordet.
- Länka roten till det sista underträdet som det vänstra underordnade underträdet till det näst sista underträdet.

Lägga till värden

Att lägga till ett värde till en skevhög är som att slå samman ett träd med en nod tillsammans med det ursprungliga trädet.

Ta bort värden

Att ta bort det första värdet i en hög kan åstadkommas genom att ta bort roten och slå samman dess underträd.

Genomförande

I många funktionella språk blir skew heaps extremt enkla att implementera. Här är ett komplett exempel på implementering i Haskell.

    
                      

        
      

            
                                 
                                 
        
                                             
                                          

           
       

           
          
           data  SkewHeap  a  =  Tom  |  Node  a  (  SkewHeap  a  )  (  SkewHeap  a  )  singleton  ::  Ord  a  =>  a  ->  SkewHeap  a  singleton  x  =  Nod  x  Empty  Tom  union  ::  Ord  a  =>  SkewHeap  a  ->  SkewHeap  a  ->  SkewHeap  a  Empty  `  union  `  t2  =  t2  t1  `  union  `  Tom  =  t1  t1  @  (  Nod  x1  l1  r1  )  `  union  `  t2  @  (  Nod  x2  l2  r2  )  |  x1  <=  x2  =  Nod  x1  (  t2  `  union  `  r1  )  l1  |  annars  =  Nod  x2  (  t1  `  union  `  r2  )  l2  insert  ::  Ord  a  =>  a  ->  SkewHeap  a  ->  SkewHeap  a  insert  x  heap  =  singleton  x  `  union  `  heap  extractMin  ::  Ord  a  =>  SkewHeap  a  ->  Kanske  (  a  ,  SkewHeap  a  )  extractMin  Empty  =  Inget  extraheraMin  (  Nod  x  l  r  )  =  Just  (  x  ,  l  `  union  `  r  )

externa länkar