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 prvek X do hromady H.
  • Min (H), vrátit minimální prvek nebo Nula pokud žádný takový prvek neexistuje.
  • Extrakční min. (H), extrahuje a vrátí minimální prvek, nebo Nula pokud žádný takový prvek neexistuje.

A ještě jedna, která ji odlišuje:[1]

  • Sloučit (H1, H2), kombinovat prvky H1 a H2 do jedné hromady.

Triviální implementace

Je jednoduché implementovat slučitelnou hromadu s jednoduchou hromadou:

Sloučit (H1, H2):

  1. x ← Extrakční min (H2)
  2. zatímco x ≠ Nil
    1. Vložka (H1, x)
    2. 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

  1. ^ 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.