Binomial hög

En binomial heap är en datastruktur som implementerar den abstrakta datatypen " priority queue ", som är en uppsättning binomialträd med två egenskaper:

nyckeln för varje nod är inte mindre än nyckeln för dess förälder;
alla binomialträd har olika storlekar.

Två konsekvenser följer av dessa egenskaper. För det första har roten till vart och ett av träden den minsta nyckeln bland sina hörn. För det andra bestämmer det totala antalet hörn i binomialhögen unikt storleken på träden som ingår i den. Till exempel består en binomial hög med hörn av tre träd med höjden 3, 2 och 0 och med 8, 4 respektive 1 element (se fig.) ${\displaystyle 13=2^{3}+2^{2}+2^{0))$

Följande operationer utförs i tid , där n är antalet hörn: $O(\log n)$

Infoga ett nytt element (amortiserat ) $O(1)$
Hitta elementet med miniminyckeln
Ta bort ett element med en miniminyckel
Minska värdet på ett givet elements nyckel
Tar bort det här objektet
Förening av två högar.

Sålunda är binomialhögen en sammanslagningshög , det vill säga, förutom de vanliga prioriterade köoperationerna (lägga till, ta bort, extrahera minimum, ändra nycklar), tillhandahåller den en ytterligare operation att slå samman två högar.

Se även

Träd (datastruktur)
Binärt sökträd Träd (grafteori) trädstruktur
Binära träd	binärt träd T-träd
Självbalanserande binära träd	AA-träd AVL-träd Röd-svart träd Splay träd träd med böter kartesiskt träd Fibonacci träd B-träd T-träd
B-träd	2-3-träd B⁺-träd B*-träd B x -träd UB-träd 2-3-4 träd (a,b)-träd dansande träd
prefix träd	suffixträd Komprimerat prefixträd Ternärt sökträd
Binär uppdelning av utrymme	k-dimensionellt träd VP-träd
Icke-binära träd	Quadtree octree Gles Voxel Octree exponentiellt träd PQ-träd
Bryter upp utrymmet	R-träd Hilbert R-träd R+-träd R*-träd X-träd M-träd Fenwick träd Segment träd
Andra träd	högen haschträd fingerträd metriskt träd Beläggning träd BK-träd Dubbelkedjat träd iDistance Länkklippt träd LSM-träd
Algoritmer	Utöka första sökningen Djup första sökning DSW-algoritm spaning tree-protokoll