Binary heap (min)

insert · extract-min O(log n)

Binární halda je úplný binární strom uložený v poli (uzel na indexu i má potomky na 2i+1 a 2i+2). Min-halda drží každého rodiče ≤ jeho potomci, takže minimum je vždy v kořeni. Insert přidá na konec a probublá nahoru; extract-min odebere kořen, přesune poslední hodnotu nahoru a nechá ji klesnout dolů. Obojí je O(log n) — takhle se staví prioritní fronty.

Min-halda
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Insert: přidej hodnotu na konec a prohazuj ji nahoru, dokud je menší než rodič.
  2. Extract-min: kořen je minimum; vrať ho.
  3. Přesuň poslední hodnotu do kořene a prohazuj ji dolů s menším potomkem, dokud se neobnoví uspořádání haldy.
  4. Index v poli řídí strom: uzel i má potomky 2i+1 a 2i+2.

Pseudokód

1insert(v):                          # O(log n)2  a.push(v); i ← a.length - 13  while i > 0 and a[i] < a[(i-1)/2]:    # smaller than parent?4    swap(a[i], a[(i-1)/2]); i ← (i-1)/2  # sift up56extractMin():                       # O(log n)7  min ← a[0]; a[0] ← a.pop()         # last value to the root8  i ← 09  loop:10    s ← the smaller child of i11    if a[i] ≤ a[s]: break12    swap(a[i], a[s]); i ← s           # sift down13  return min