Sloučitelná hromada - Mergeable heap
v počítačová věda, a slučitelná hromada (také nazývaný a tvárná hromada) je abstraktní datový typ, což je halda podpora operace sloučení.
Definice
Sloučitelná halda podporuje obvyklé operace haldy:[1]
Make-Heap ()
, vytvořte prázdnou hromadu.Vložit (H, x)
, vložte prvekX
do hromadyH
.Min (H)
, vrátit minimální prvek neboNula
pokud žádný takový prvek neexistuje.Extrakční min. (H)
, extrahuje a vrátí minimální prvek, neboNula
pokud žádný takový prvek neexistuje.
A ještě jedna, která ji odlišuje:[1]
Sloučit (H1, H2)
, kombinovat prvkyH1
aH2
do jedné hromady.
Triviální implementace
Je jednoduché implementovat slučitelnou hromadu s jednoduchou hromadou:
Sloučit (H1, H2):
x ← Extrakční min (H2)
zatímco x ≠ Nil
Vložka (H1, x)
x ← Extrakční min (H2)
To však může být zbytečné jako každý jiný Extrakční min. (H)
a Vložit (H, x)
obvykle musí udržovat halda vlastnost.
Efektivnější implementace
Příklady sloučitelných datových struktur haldy zahrnují:
Úplnější seznam se srovnáním výkonu najdete na Halda (datová struktura) § Porovnání teoretických mezí pro varianty.
Ve většině sloučitelných struktur haldy je sloučení základní operací, na které jsou založeny ostatní. Vložení je implementováno sloučením nové haldy s jedním prvkem s existující haldy. Odstranění je implementováno sloučením potomků odstraněného uzlu.
Viz také
Reference
- ^ A b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Úvod do algoritmů (3. vyd.). MIT Press a McGraw-Hill. 505–506. ISBN 0-262-03384-4.