Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Halda

Definice

Halda(heap) je dynamická množina se stromovou strukturou (binární halda je binární strom), pro kterou platí tzv. vlastnost haldy:

Je-li potomek , pak

Haldy s touto nerovností jsou tzv. min-heapy, pokud je nerovnost opačná, jde o max-heap.

(Binární) haldy

Binární haldy jsou nejčastějším typem haldy. Zajišťují nalezení minimálního prvku v konstantním čase a odebrání a přidání minima v čase . V každé hladině od první až do předposlední je max. možný počet uzlů, v poslední jsou uzly co nejvíce vlevo - tedy max. výška haldy s prvky je . Proto je pro binární haldy jednoduše proveditelná jejich datová reprezentace polem (bez pointerů), kde při indexování od 0 má uzel na indexu :

- Levého a pravého syna na indexu , resp. (pokud to není víc než celk. počet prvků, potom syny nemá).
- Rodiče na indexu .

Přidání uzlu do haldy znamená přidání prvku na konec haldy a dokud má jeho rodič větší klíč, jeho prohazování s rodičem (tedy posouvání o vrstvu výš). Při odebírání uzlu z haldy tento nahradím posledním prvkem v haldě a potom dokud neplatí vlastnost haldy (nejméně jeden z potomků má menší klíč), prohazuji ho s potomkem s menším klíčem (a posouvám o vrstvu níž).

Vytvoření haldy je možné v čase , kde je počet prvků v haldě - přidání 1 prvku do haldy trvá , kde je aktuální výška (a roste od 0 až k , počet prvků ve výšce je , bereme-li výšku listů rovnou nule) - v součtu za všechny prvky jde o .

Binární halda se používá např. k třídění haldou (heapsortu), kdy se z dat, která je potřeba utřídit, nejdříve postaví halda, a potom se opakuje operace odebrání kořene (tj. minimálního prvku).

Fibonacciho haldy

Fibonacciho haldy mají nízkou časovou složitost běžných operací - amortizovaně pro vložení, hledání minima apod.; odebrání prvku a odebrání minima má složitost pro prvků v haldě. Tvoří ji skupina stromů, vyhovujících vlastnosti haldy. Každý uzel haldy s prvky má max. potomků a ve svém podstromě minimálně uzlů, kde je -té Fibonacciho číslo. To je zajištěno pravidlem, že při odebírání prvků lze z nekořenového uzlu oddělit max. 1 syna, jinak je nutné oddělit i tento uzel a ten se pak stane kořenem dalšího stromu. Počet stromů se snižuje při odebírání minima, kdy jsou spojovány dohromady.

Fibonacciho haldy se používají pro efektivní implementaci složitějších operací, jako např. Jarníkova nebo Dijkstrova algoritmu.

<#4913#>4915>>