Referanseside · Kapittel 6

Begreper & formler

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

Øv med flashcards8 kort fra dette kapittelet

Begreper

Sentrale begreper fra kapittelet med korte definisjoner.

01Heap

Et binærtre representert i array der hver node oppfyller heap-egenskapen (forelder ≥ barn i maks-heap).

02Heap-egenskap

For maks-heap: $A [parent (i)] \geq A [i]$ .

03Build-Heap

Prosess som gjør et vilkårlig array om til en gyldig heap i $O (n)$ tid.

04Heapify

Operasjon som gjenoppretter heap-egenskapen fra en node nedover i treet.

05Priority Queue

Abstrakt struktur som støtter ‘insert’ og ‘extract-max’ i $O (lo g n)$ tid.

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

Left (i) = 2 i, Right (i) = 2 i + 1, Parent (i) = ⌊ i /2 ⌋

T (n) = O (n)

T (n) = O (n lo g n)