Rešitev: Iz podatkov sestavi MAX kopico

Iz MaFiRaWiki

Naloga: Iz podatkov sestavi MAX kopico

Ker je kopica dvojiško drevo, najprej definiramo osnovne operacije dvojiškega drevesa.

Clear[Pripravi, DDrevo, Sestavi, Koren, LeviSin, DesniSin, JePrazno]
Pripravi[] := DDrevo[]
Sestavi[p_, ls_, ds_] := DDrevo[ls, p, ds]
Koren[DDrevo[_, k_, _]] := k
LeviSin[DDrevo[l_, _, _]] := l
DesniSin[DDrevo[_, _, d_]] := d
JePrazno[d_DDrevo] := Length[d] == 0
Clear[Oce, Ls, Ds, Zamenjaj, UrediElement]

Definirajmo pomožne funkcije Oce, Ls in Ds, pri čemer je Ls levi sin, Ds pa desni.

Oce[i_] := Floor[i/2]
Ls[i_] := 2 i
Ds[i_] := 2 i + 1

Definirajmo še ostale operacije. Funkcija Zamenjaj v seznamu L zamenja vrednosti na pozicijah i in j.

Zamenjaj[L_List, i_Integer, j_Integer] := ReplacePart[ReplacePart[L, L[[j]], i], L[[i]], j]

Funkcija UrediElement je ukaz, ki vrne seznam, v katerem je drevo s korenom i kopica.

UrediElement[L_List, i_Integer, n_Integer] := Module[{l, d, vecji},
   l = Ls[i];
   d = Ds[i];
   If[l ≤ n && L[[l]] > L[[i]], vecji = l, vecji = i];
   If[d ≤ n && L[[d]] > L[[vecji]], vecji = d];
   If[vecji ≠ i, UrediElement[Zamenjaj[L, i, vecji], vecji, n], L]
   ]
Clear[MaxKopica]
MaxKopica[L_List] := Module[{i, M = L, n},
   n = Length[M];
   For[i = Oce[n], i ≥ 1, i--,
     M = UrediElement[M, i, n];
     ];
   M
   ]

Poglejmo na primeru

Clear[s]
s = {11, 16, 8, 24, 13, 25, 17, 12, 19};
MaxKopica[s]

Ukaz MaxKopica[s] vrne

{25, 24, 17, 19, 13, 8, 11, 12, 16}


Glej tudi

Osebna orodja