Referanseside · Kapittel 19

Begreper & formler

Alle nøkkelbegrepene og formlene fra Fibonacci-heap, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.

Øv med flashcards7 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Heap-egenskap

Forelder ≤ barn (min-heap).

02Amortisert tid

Analyse viser at flere operasjoner blir billigere i gjennomsnitt.

03Consolidation

Sammenslåing av trær med samme grad etter ‘extract-min’.

04Decrease-Key

Reduserer verdien av en node og kutter den fra forelderen ved behov.

05Potensiell metode

Brukt for å vise amortisert kompleksitet.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

Insert : O (1), Union : O (1), Extract-Min : O (lo g n), Decrease-Key : O (1)

max grad = O (lo g n)