Disjunktní množiny (Union-Find)
Uvažujme implementaci pomocí stromů s heuristikou union by rank (ale bez komprese cest). Ukažte posloupnost operací Make-Set, Union a Find-Set délky m, z nichž n operací je Make-Set, takovou, že její časová složitost je fi(m log n).
Disjunktní množiny (Union-Find)
Chceme přidat operaci Print-Set(x), která vypíše všechny prvky v množině, do které patří prvek x. Jakým způsobem upravit implementaci, aby Print-Set bylo lineární vůči velikosti množiny a složitosti ostatních operací se nezhoršily?
► v případě implementace pomocí zřetězených seznamů (plytkých stromů)
► v případě implementace pomocí stromů s union by rank a kompresí cest
Disjunktní množiny (Union-Find)
Operace Union se ve skutečnosti skládá ze dvou operací: Find-Set a Link. Ukažte, že posloupnost m operací Make-Set, Link a Find-Set, v níž se všechny operace Link objevují před první operací Find-Set, má složitost O(m).
Proč stejná úvaha nefunguje ve chvíli, kdy se operace můžou libovolně míchat?
Aplikace disjunktních množin
Offline minimum
Máme předem dánu posloupnost operací Insert(x) a Extract-Min. Vkládané prvky jsou z množiny {1,..., n} a každý prvek je vložen právě jednou. Úkolem je vypsat posloupnost prvků, které by postupně vracely operace Extract-Min.
Příklad: 1(4), 1(8), E, 1(3), E, 1(9), 1(2), 1(6), E, E, E, 1(1), 1(7), E, 1(5).
1. Jaký bude výstup pro výše uvedený příklad?
2. Jak řešit tento problém obecně? S jakou složitostí?