Popište operace vložení prvku a odebrání minima binární minimové haldy a jejich časové složitosti.

HeapInsert

• Vložení prvku do haldy

→ vlastnost tvaru haldy dovoluje přidat okamžitě nový prvek nejspodnější hladiny

1. pokud by hladina byla již plná založíme novou hladinu
2. pokud je uspořádání mezi novým listel l a jeho předkem p v pořádku, můžeme skončit, pokud není nespľňuje tuto vlastnost, prohodíme k(l) a k(p)
3. → krokem 2 se může porušit vlastnost Haldového uspořádání mezi vrcholem p a předkep p
   • pokud tomu tak je opakujeme krok 2

→ opakuje dokud vlastnost není splněna nebo se k(l) nedostane až do kořene

HeapInsert(halda H, klíč k)
{
	H.push_back(k);
	v = H.size()-1;
	
BubbleUp(v)

}

BubbleUp(v):
{
	Dokud není p kořen:
		p := předek(v)
		Pokud k(p) <= k(v):
			return

		swap(k(v), k(p))
		v := p
}

Na každé hladině strávíme O(1) operací a procházených hladin je nejvýše logaritmicky mnoho, celkem tedy O(log n).

HeapExtractMin

• skládá se z nalezení minima a jeho následné ostranění

HeapFindMin(H)

• triviální → díky vlastnostem haldy je vždy minimum vždy v kořeni stromu

⇒ časová složitost : O(1)

HeapExtractMin(H)

• složitější → odstranění kořene by způsobilo porušení vlastnosti tvaru haldy