Halda (datová struktura): Porovnání verzí

Z Wikipedie, otevřené encyklopedie
Smazaný obsah Přidaný obsah
ArthurBot (diskuse | příspěvky)
Luckas-bot (diskuse | příspěvky)
m robot přidal: hu:Kupac (adatszerkezet)
Řádek 166: Řádek 166:
[[fr:Tas (informatique)]]
[[fr:Tas (informatique)]]
[[he:ערימה (מבנה נתונים)]]
[[he:ערימה (מבנה נתונים)]]
[[hu:Kupac (adatszerkezet)]]
[[is:Hrúga (tölvunarfræði)]]
[[is:Hrúga (tölvunarfræði)]]
[[it:Heap]]
[[it:Heap]]

Verze z 14. 2. 2010, 06:43

Tento článek se zabývá haldou jako stromovou datovou strukturou. Pro haldu jako paměťový prostor v počítačových programech hledejte viz Dynamická alokace paměti.

Halda je v informatice stromová datová struktura splňující tzv. vlastnost haldy: pokud je B potomek A, pak x(A) >= x(B). To znamená, že v kořenu stromu je vždy prvek s nejvyšším klíčem (klíč udává funkce x). Taková halda se pak někdy označuje jako max heap (heap je v angličtině halda), halda s reverzním pořadím prvků se analogicky nazývá min heap. Díky této vlastnosti se haldy často používají na implementaci prioritní fronty. Efektivita operací s haldou je klíčová pro mnoho algoritmů.

Operace s haldou

  • INSERT - přidání nového prvku do haldy
  • DELETE MAX nebo DELETE MIN - vyjmutí kořenu v max heap nebo v min heap
  • DELETE(v) - smaže uzel „v“
  • MIN, MAX - vrátí minimální resp. maximální klíč v haldě
  • DECREASE KEY(v, okolik) - zmenšení klíče uzlu „v“ o hodnotu „okolik“
  • INCRESE KEY(v, okolik) - zvětšení klíče uzlu „v“ o hodnotu „okolik“
  • MERGE - spojení dvou hald do jedné nové validní haldy obsahující všechny prvky obou původních
  • MAKE - dostane pole N prvku a vytvoří z nich haldu

Popis haldy

Haldu bychom mohli tedy definovat jako datovou struktura splňující dvě základní podmínky:

  • lokální podmínku na uspořádání - prvek reprezentující otce je menší než prvek reprezentovaný synem apod.
  • strukturální podmínku na stromy, ze kterých jsou vytvořené

Právě podle těchto podmínek se haldy rozdělují na d-regulární, Fibonacciho, Leftist a další (mohou se lišit jak lokální, tak strukturální podmínkou).

Jak již bylo naznačeno, rozlišujeme haldy Min-Heap a Max-Heap.

  • U Min-Heap jsou klíče dětí jednoho uzlu vždy větší než klíče svého otce. To způsobuje, že na kořenech stromu lze nalézt pouze prvek s minimálním klíčem.
  • Opačně je pro Max-Heap stanovena podmínka, že klíče dětí jednoho uzlu musí být vždy menší než klíče jejich otce. Zde se na kořeni stromu vždy nachází prvek s maximálním klíčem.

Příklady Max-Heap a Min-Heap:

Max heap
Max heap
Min heap
Min heap


Matematicky se u obou variant jedná pouze o rozdíl v jejich opačném pořadí prvků. Protože je definice vzestupně i sestupně libovolná, je pouze otázkou interpretace, zda se u konkrétní implementaci jedná o Min-Heap nebo o Max-Heap.

Obousměrné haldy (Double heaps)

Často se stává, že halda má zobrazit podmínku v obou směrech. V tomto případě se jednoduše vytvoří haldy dvě a uspořádají se podle větší a menší relace. Taková struktura je pak označována jako Double heap nebo krátce Deap.

Při použití Double heaps je třeba dávat pozor na to, že ne každá implementace haldy si pro jednotlivé operace zachová svůj průběh. Například Fibonacciho haldy s konstantním amortizovaným průběhem podporují pouze decreaseKey pro snížení klíčů. Všeobecný changeKey pro změnu klíče, který je vyžadován v případě Double heap, potřebuje ale amortizovaně minimálně logaritmický čas.

Variantou hald, které splňují podmínku haldy pouze částečně, nebo odchylně jsou tzv. Min-Max-Heap. Jedná se o Double heap, které díky odchylné formě podmínky haldy mohou udržovat data pouze v jednom stromu.

Varianty haldy

Existuje mnoho druhů hald s rozdílným průběhem pro různé operace. Příklady hald:

Porovnání teoretických hranic složitostí pro jednotlivé varianty

Následující složitosti[1] jsou pro nejhorší případ u Pairing, binární a binomiální haldy. a amortizovaná složitost u Fibonacciho a Leftist haldy. O(f) dává asymptotickou horní hranici a Θ(f) je asymptoticky přesná (až na multiplikativní konstantu) složitost. V tabulce přepokládáme použití Min Heap

Operace Binární Binomiální Fibonacciho Pairing Leftist 2-3 Treap Beap
createHeap Θ(1) Θ(1) Θ(1) Θ(1)
findMin Θ(1) O(lg n) or Θ(1) Θ(1)
deleteMin Θ Θ Θ Θ Θ
insert Θ Θ Θ Θ Θ or Θ
decrease-key Θ Θ Θ Θ Θ or Θ
merge Θ Θ Θ Θ Θ or Θ

Využití haldy

Halda má široké spektrum využití a patří mezi oblíbené datové struktury pro mnoho aplikací.

  • Heapsort : Jedna z nejrychlejších metod třídění.
  • Výběrový algoritmus' : Hledání minima, maxima nebo obou, medianu nebo dokonce jakehokoli k-prvku a může být prováděno dynamicky.
  • implementace Dijkstrova algoritmu - využití Fibonacciho haldy.
  • implementace Jarníkova algoritmu
  • Prioritní fronty : využití haldy pro stanovení front úkolů u serverů nebo provozních systémů
  • Hladové algoritmy : halda představuje ideální datovou strukturu pro tzv. hladové algoritmy, které se řídí lokálními optimalizovanými rozhodnutími.

Implementace haldy

Standard Template Library jazyka C++ poskytuje algoritmy make_heap, push_heap a pop_heap pro binární haldy, které pracují na iterátorech s náhodným přístupem.

Implementace binární haldy

Zajímavé je, že binární haldy mohou být implementovány jednoduše pomocí pole.

Reprezentace Bin. haldy polem

První nebo poslední prvek bude obsahovat kořen. Následující dva prvky pole obsahují jeho potomky. Následující čtyři obsahují další čtyři potomky předchozích dvou potomků, atd. A tak potomci uzlu na pozici n budou na pozici 2n a 2n+1 v polích indexovaných od jedničky nebo 2n+1 a 2n+2 v polích indexovaných od nuly. Vyvažování haldy je prováděno záměnou prvků, které nejsou umístěny ve správném pořadí. Tak, jako můžeme sestavit haldu z pole bez využití další paměti (například pro uzly), heapsort může být také použít pro třídění pole na místě. Další výhoda haldy v některých aplikacích je, že sestavení hald může být prováděno v lineárním čase použitím Tarjanova algoritmu.

Poznámky

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill.

Externí odkazy