Binomiaalinen kasa

Binomikaso on tietorakenne , joka toteuttaa abstraktin tietotyypin " prioriteettijono ", joka on joukko binomipuita , jolla on kaksi ominaisuutta:

kunkin solmun avain ei ole pienempi kuin sen emolaitteen avain;
kaikki binomiaaliset puut ovat erikokoisia.

Näistä ominaisuuksista seuraa kaksi seurausta. Ensinnäkin jokaisen puun juurella on pienin avain sen kärjestä. Toiseksi, binomiaalisen kasan kärkien kokonaismäärä määrittää yksiselitteisesti siihen sisältyvien puiden koon. Esimerkiksi binomikaso, jossa on pisteet, koostuu kolmesta puusta, joiden korkeus on 3, 2 ja 0 ja joissa on vastaavasti 8, 4 ja 1 elementtiä (katso kuva). $13=2^{3}+2^{2}+2^{0}$

Seuraavat toiminnot suoritetaan ajassa , jossa n on pisteiden lukumäärä: $O(\log n)$

Uuden elementin lisääminen (poisto ) $O(1)$
Elementin löytäminen minimiavaimella
Elementin poistaminen minimiavaimella
Tietyn elementin avaimen arvon pienentäminen
Poistetaan tätä kohdetta
Kahden kasan liitto.

Siten binomiaalinen kasa on yhdistävä kasa , eli se tarjoaa tavallisten prioriteettijonotoimintojen (lisääminen, poistaminen, vähimmäismäärän purkaminen, avainten vaihtaminen) lisäksi lisätoiminnon kahden kasan yhdistämiseksi.

Katso myös

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla