Binomická hromada

Binomická halda je datová struktura , která implementuje abstraktní datový typ „ prioritní fronta “, což je sada binomických stromů se dvěma vlastnostmi:

klíč každého uzlu není menší než klíč jeho rodiče;
všechny binomické stromy mají různé velikosti.

Z těchto vlastností vyplývají dva důsledky. Za prvé, kořen každého ze stromů má mezi svými vrcholy nejmenší klíč. Za druhé, celkový počet vrcholů v binomické hromadě jednoznačně určuje velikost stromů v ní obsažených. Například binomická hromada s vrcholy se skládá ze tří stromů o výšce 3, 2 a 0 a majících 8, 4 a 1 prvky (viz obr.) ${\displaystyle 13=2^{3}+2^{2}+2^{0))$

Následující operace se provádějí v čase , kde n je počet vrcholů: $O(\log n)$

Vložení nového prvku (amortizovaného ) $O(1)$
Nalezení prvku pomocí minimálního klíče
Odstranění prvku s minimálním klíčem
Snížení hodnoty klíče daného prvku
Odstranění této položky
Spojení dvou hromad.

Binomická halda je tedy slučovací halda , to znamená, že kromě standardních prioritních operací s frontou (přidání, mazání, vyjmutí minima, změna klíčů) poskytuje další operaci sloučení dvou hald.

Viz také

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree