Binomiális kupac

A  binomiális kupac egy olyan adatstruktúra , amely a „ prioritási sor ” elvont adattípust valósítja meg, amely két tulajdonsággal rendelkező binomiális fák halmaza :

• az egyes csomópontok kulcsa nem kisebb, mint a szülő kulcsa;
• minden binomiális fa különböző méretű.

Ezekből a tulajdonságokból két következmény következik. Először is, mindegyik fa gyökerének van a legkisebb kulcsa a csúcsai között. Másodszor, a binomiális kupac csúcsainak teljes száma egyértelműen meghatározza a benne lévő fák méretét. Például egy binomiális kupac csúcsokkal három fából áll, amelyek magassága 3, 2 és 0, illetve 8, 4 és 1 elemből áll (lásd az ábrát).

A következő műveleteket hajtjuk végre időben , ahol n a csúcsok száma:

• Új elem beszúrása (amortizált )
• Az elem megkeresése a minimális kulccsal
• Elem eltávolítása minimális kulccsal
• Egy adott elem kulcsának értékének csökkentése
• Az elem törlése
• Két kupac egyesülése.

Így a binomiális kupac egy összevonó kupac , azaz a szabványos prioritási sorműveleteken (hozzáadás, törlés, minimum kivonás, kulcsok megváltoztatása) mellett egy további műveletet is biztosít két kupac egyesítésére.

Lásd még

• bináris kupac
• fibonacci kupac