Mound - online puzzle

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“

INCREASE 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 prvků a vytvoří z nich haldu

Popis haldy

Haldu bychom mohli tedy definovat jako datovou strukturu 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.