Grămada binomială

Un  heap binomial este o structură de date care implementează tipul de date abstract „ coadă de prioritate ”, care este un set de arbori binomi cu două proprietăți:

• cheia fiecărui nod nu este mai mică decât cheia părintelui său;
• toți arborii binomi au dimensiuni diferite.

Din aceste proprietăți decurg două consecințe. În primul rând, rădăcina fiecărui copac are cea mai mică cheie dintre vârfurile sale. În al doilea rând, numărul total de vârfuri din heap-ul binom determină în mod unic dimensiunea copacilor incluși în acesta. De exemplu, o grămadă binomială cu vârfuri constă din trei arbori cu înălțimea 3, 2 și 0 și având 8, 4 și respectiv 1 elemente (vezi Fig.)

Următoarele operații sunt efectuate în timp , unde n este numărul de vârfuri:

• Introducerea unui element nou (amortizat )
• Găsirea elementului cu cheia minimă
• Îndepărtarea unui element cu o cheie minimă
• Scăderea valorii cheii unui element dat
• Se șterge acest articol
• Unirea a două grămezi.

Astfel, heap-ul binom este un heap de fuziune , adică pe lângă operațiunile standard cu prioritate în coadă (adăugarea, ștergerea, extragerea minimului, schimbarea cheilor), oferă o operațiune suplimentară de îmbinare a două heap-uri.

Vezi și

• morman binar
• gramada de Fibonacci