Parningshög
| Parningshög | |||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Typ | högen | ||||||||||||||||||
| Uppfunnet | 1986 | ||||||||||||||||||
| Uppfunnet av | Michael L. Fredman, Robert Sedgewick, Daniel Sleator och Robert Endre Tarjan | ||||||||||||||||||
| Tidskomplexitet i stor O-notation | |||||||||||||||||||
| |||||||||||||||||||
En parningshög är en typ av högdatastruktur med relativt enkel implementering och utmärkt praktisk amorterad prestanda, introducerad av Michael Fredman , Robert Sedgewick , Daniel Sleator och Robert Tarjan 1986. Parhögar är högordnade flervägsträdstrukturer och kan vara anses förenklade Fibonacci-högar . De anses vara ett "robust val" för att implementera sådana algoritmer som Prims MST-algoritm och stöder följande operationer (förutsatt att det är en min-hög):
- find-min : returnera helt enkelt det översta elementet i högen.
- meld : jämför de två rotelementen, det mindre förblir roten till resultatet, det större elementet och dess underträd läggs till som ett underordnat av denna rot.
- infoga : skapa en ny hög för det infogade elementet och smält in i den ursprungliga högen.
- minska-tangent (valfritt): ta bort underträdet som är rotat vid nyckeln som ska minskas, ersätt nyckeln med en mindre nyckel och smält sedan resultatet tillbaka till högen.
- delete-min : ta bort roten och gör upprepade sammanslagningar av dess underträd tills ett träd finns kvar. Olika sammanslagningsstrategier används.
Analysen av sammankopplingshögarnas tidskomplexitet inspirerades från början av den för splayträd . Den avskrivna tiden per raderingsminut är O (log n ) , och operationerna find-min , meld och infoga körs i O (1) amorterad tid.
När en minskningsknappsoperation också läggs till, har det visat sig vara svårt att bestämma den exakta asymptotiska körtiden för parningshögar. Ursprungligen antogs tidskomplexiteten för denna operation på empiriska grunder vara O (1) , men Fredman bevisade att den amorterade tiden per minskningsnyckel är minst för vissa operationssekvenser. Med hjälp av ett annat amorteringsargument bevisade Pettie sedan att insert , meld , och reduce-key alla körs i amorterad tid, vilket är . Elmasry introducerade senare utarbetningar av parningshögar (lata, konsolidera) för vilka minska-nyckelkörningar i avskriven tid och andra operationer har optimala amorterade gränser, men ingen tight bunden är känd för den ursprungliga datastrukturen.
Även om den asymptotiska prestandan för parningshögar är sämre än andra prioritetsköalgoritmer som Fibonacci-högar , som utför minskningsnyckel i amorterad tid, är prestandan i praktiken utmärkt. Jones och Larkin, Sen och Tarjan genomförde experiment med att para ihop heaps och andra heapdatastrukturer. De drog slutsatsen att d-ary heaps såsom binära heaps är snabbare än alla andra heapimplementeringar när reducering-tangenten inte behövs (och därför finns det inget behov av att externt spåra nodernas placering i heapen), men att när reducering -nyckel behövs parningshögar är ofta snabbare än d-ary-högar och nästan alltid snabbare än andra pekarbaserade heaps, inklusive datastrukturer som Fibonacci-högar som är teoretiskt mer effektiva. Chen et al. undersökte prioritetsköer specifikt för användning med Dijkstras algoritm och drog slutsatsen att användning av en d-ary-hög utan reduceringsnyckel (istället för att duplicera noder på högen och ignorera redundanta instanser) resulterade i bättre prestanda, trots de sämre teoretiska prestandagarantierna.
Strukturera
En parningshög är antingen en tom hög, eller ett parningsträd som består av ett rotelement och en möjligen tom lista med parningsträd. Högbeställningsegenskapen kräver att föräldern till någon nod inte är större än själva noden. Följande beskrivning förutsätter en rent funktionell hög som inte stöder sänktangentoperationen .
typ PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]]) typ PairingHeap[Elem] = Tom | PairingTree[Elem]
En pekarbaserad implementering för RAM-maskiner , som stöder minska-nyckel, kan uppnås med hjälp av tre pekare per nod, genom att representera barnen i en nod med en enkellänkad lista: en pekare till nodens första barn, en till dess nästa syskon , och en till sitt tidigare syskon (eller, för syskon längst till vänster, till sin förälder). Alternativt kan föregående-pekaren utelämnas genom att låta det sista barnet peka tillbaka till föräldern, om en enda boolesk flagga läggs till för att indikera "slut på listan". Detta ger en mer kompakt struktur på bekostnad av en konstant overheadfaktor per operation.
Operationer
hitta-min
Funktionen find-min returnerar helt enkelt rotelementet i högen:
funktion find-min(heap: PairingHeap[Elem]) -> Elem om heap är Tomt fel annars returnera heap.elem
smälta samman
Att smälta med en tom hög returnerar den andra högen, annars returneras en ny hög som har minimum av de två rotelementen som sitt rotelement och lägger bara till högen med den större roten till listan över underhögar:
funktion meld(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem] om heap1 är Empty return heap2 elsif heap2 är Empty return heap1 elsif heap1.elem < heap2.elem return Heap(heap1.elem, heap2 :: heap1. subheaps) annars returnera Heap(heap2.elem, heap1 :: heap2.subheaps)
Föra in
Det enklaste sättet att infoga ett element i en hög är att smälta samman högen med en ny hög som bara innehåller detta element och en tom lista med underhögar:
function insert(elem: Elem, heap: PairingHeap[Elem]) -> PairingHeap[Elem] return meld(Heap(elem, []), heap)
radera-min
Den enda icke-triviala grundläggande operationen är raderingen av minimielementet från högen. Detta kräver att man utför upprepade sammansmältningar av sina barn tills bara ett träd finns kvar. Standardstrategin smälter först underhögarna i par (detta är steget som gav denna datastruktur dess namn) från vänster till höger och smälter sedan samman den resulterande listan med högar från höger till vänster:
funktion delete-min(heap: PairingHeap[Elem]) -> PairingHeap[Elem] om heap är Empty error annars returnerar merge-pairs(heap.subheaps)
Detta använder hjälpfunktionen merge-pairs :
funktion merge-pairs(lista: Lista[PairingTree[Elem]]) -> PairingHeap[Elem] if length(list) == 0 return Tom elsif length(list) == 1 returlista [0] else return meld(meld( list[0], list[1]), merge-pairs(list[2..]))
Att detta verkligen implementerar den beskrivna tvåpassage vänster-till-höger sedan höger-till-vänster sammanslagningsstrategi kan ses från denna minskning:
sammanfoga-par([H1, H2, H3, H4, H5, H6, H7]) => meld(meld(H1, H2), sammanfogade-par([H3, H4, H5, H6, H7])) # meld H1 och H2 till H12, sedan resten av listan => meld( H12 , meld(meld(H3, H4), merge-par([H5, H6, H7]))) # meld H3 och H4 till H34, sedan resten av listan => meld(H12, meld( H34 , meld(meld(H5, H6), merge-pairs([H7])))) # meld H5 och H6 till H56, sedan resten av listan = > meld(H12, meld(H34, meld( H56 , H7))) # byt riktning, smält de två sista resulterande högarna, vilket ger H567 => meld(H12, meld(H34, H567 )) # meld de två sista resulterande högarna , vilket ger H34567 => meld(H12, H34567 ) # slutligen, smält det första paret med resultatet av att slå samman resten => H1234567
Sammanfattning av löptider
Här är tidskomplexiteten för olika högdatastrukturer. Funktionsnamn antar en min-hög. För betydelsen av " O ( f )" och " Θ ( f )" se Big O-notation .
| Drift | hitta-min | radera-min | Föra in | minska-knappen | smälta samman |
|---|---|---|---|---|---|
| Binär | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
| Vänsterman | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
| Binom | Θ (1) | Θ (log n ) | Θ (1) | Θ (log n ) | O (log n ) |
| Fibonacci | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Parning | Θ (1) | O (log n ) | Θ (1) | o (log n ) | Θ (1) |
| Brodal | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Rank-parning | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Strikt Fibonacci | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| 2–3 högar | O (log n ) | O (log n ) | O (log n ) | Θ (1) | ? |
externa länkar
- Louis Wasserman diskuterar parningshögar och deras implementering i Haskell i The Monad Reader, nummer 16 (sid. 37–52).
- parningshögar , Sartaj Sahni