Kopiec - to drzewo binarne, które jest wypełnione na wszystkich poziomach (wyjątek stanowi ostatni poziom, który jest wypełniony od lewej do pewnego miejsca) charakteryzujące się tym, że rodzic ma zawsze większą

wartość aniżeli potomkowie (patrz rysunek 1). Kopiec binarny może być zaimplementowany jako tablicowa struktura danych, wówczas każdy węzeł odpowiada elementowi tablicy, w którym podana jest wartość węzła. Korzeniem takiego kopca jest pierwszy element tablicy. Indeksy potomków oraz rodzica węzła i można łatwo policzyć. Indeks lewego potomka węzła irówna się :

LEFT( i ) = i * 2

Przykładowy kopiec

Przykładowy kopiec jako struktura tablicowa :

18 12 10 11 9 8 4 5 7

Dodawanie liczb binarnych

Reszta := 0

for i := 1 to n do

begin

C[i] :=[A[i] + B[i] + Reszta] mod 2

Reszta := (A[i] + B[i] + Reszta) div 2

C[i+1] := Reszta

end

Sortowanie przez scalanie (angielskie mergesort), rekurencyjny algorytm sortowania wdrażający zasadę “dziel i zwyciężaj” w sposób następujący:

1) n-elementowy ciąg dzieli się na dwa podciągi n/2-elementowe;

2) otrzymane podciągi sortuje się, używając rekurencyjnie sortowanie przez scalanie;

3) na każdym poziomie scala się posortowane podciągi w jeden posortowany podciąg.

Złożoność sortowania przez scalanie wynosi O(n log n).

Przykład:

MERGE - SORT (A, p, n)

if p < n then

q := ( p + n ) div 2

MERGE - SORT (A, p, q )

MERGE - SORT (A, q + 1, r )

MERGE (A, p, q, r)

MERGE (A, p, q, r)

i:=p

j:=q+1

k:=p

while i <= q and j<=r do

if A[i] > A[j] then

begin

B[k]:=A[j]

j:=j+1

k:=k+1

end

else

B[d]:=A[i]

i:=i+1

k:=k+1

if i>q then

begin

for j=j to r do

B[k] :=A[j]

k:=k+1

end

else

for i=i to q do

B[k]:=A[i]

k:=k+1

Sortowanie przez wstawianie (angielskie insertsort), algorytm sortowania odpowiadający sposobowi porządkowania talii kart:

1) pierwszą kartę umieszcza się w pustej ręce;

2) każdą następną podniesioną ze stołu kartę porównuje się od lewej do prawej (lub metodą wyszukiwania binarnego) z trzymanymi już w ręce i wstawia na właściwe miejsce.

Złożoność sortowania przez wstawianie wynosi O(n2).

Przykład:

A [ 1 . . n ]

INSERT - SORT

i = 1

j = 1

for j = 2 to lenght [ A] do

key = A [ j ]

i = j - 1

while i > 0 and A [ i ] > key do

A [ i + 1 ]:= A [ i ]

i := i - 1

A [ i + 1 ] := key

Sortowanie przez kopcowanie (angielskie heapsort), algorytm opracowany przez J. W. J. Williamsa w 1964, sortujący tablicę w miejscu za pomocą jednorazowej operacji zbudowania kopca w całej tablicy i wzajemnego zamieniania skrajnych elementów tablicy redukowanej z krokiem 1, połączonego z przywracaniem każdej zredukowanej tablicy własności kopca, aż do osiągnięcia kopca rozmiaru 2. Złożoność sortowania przez kopcowanie wynosi O(n log n).

Przykład:

BuliD-HEAP [A]

Heap - size [A] := length [A]

for I= length [A] div 2 downto 1 do

Heapifi [A, i]

HEAP - SORT ( A )

BUILD - HEAP ( A )

For i = length [ A ] downto 2 do

Zamień A [1] :=A [ i ]

HEAP - SIZE ( A ):= HEAP - SIZE ( A - 1 )

HEAPIFY ( A, 1 )

Sortowanie bąbelkowe (angielskie bubble sort), sortowanie polegające na przeglądaniu po kolei elementów porządkowanego ciągu i zamienianiu miejscami sąsiadujących elementów tak, aby spełniały relację porządkującą; w ten sposób elementy mniejsze (“lżejsze”) przesuwają się na początek ciągu.

Przykład:

z = true

while z = true do

begin

z = false

for i=1 to n - 1 do

begin

if A [ i ] = A [ i + 1 ] then

r = A [ i + 1 ]

A [ i + 1 ] = A [ i ]

A [ i ] = r

z = true

end

end

Quick Sort

Jest to jeden z najszybszych algorytmów sortowania, klasy O(N log2N). Autorem jego jest C.A.Hoare.

Procedura sortowania dzieli się na dwie części:

a) część służącą do właściwego sortowania (tzn. wywoływania samego siebie - rekurencji)

b) procedury rozdzielania elementów tablicy względem pewnej wartości komórki tablicy służącej za oś podziału. Sortowanie jest wykonywane właśnie przez tę procedurę, a rekurencja zapewnia "sklejenie" wyników cząstkowych i w konsekwencji posortowanie całej tablicy.

Przykład

Quicksort (A, p, r)

if p<r then

begin

q:=PARTITION (A, p, r)

Quicksort (A, p, q)

Quicksort (A, q+1, r)

end

Partition (A, p, r)

x:=A[p]

i:=p-1

j:=r+1

while true do

begin

repeat j:=j-1

until A[j] <= x

repeat I:=i+1

until A[i] >=x

if I< j then

zmien A[i] <-> A [j]

else return j

end

Drzewa binarne

Drzewa binarne są szczególnym rodzajem drzew (drzewo - graf acykliczny, w którym można wyróżnić jeden wierzchołek jako korzeń). Każdy wierzchołek ma co najwyżej 2 następniki, które potocznie nazywane są 'lewym' i 'prawym'. Dodatkowo wiadomo, że wartość przechowywana w następniku lewym jest mniejsza, a w następniku prawym większa od wartości przechowywanej w omawianym wierzchołku (wynika stąd, że w drzewie binarnym elementy nie mogą się powtarzać). Na tym nie koniec. Załóżmy, że mamy wierzchołek W i jego lewy następnik L. Nie tylko wartość przechowywana w L jest mniejsza od wartości w W, ale również mniejsze od wartości W są wszystkie wartości leżące w poddrzewie, którego korzeniem jest L.

Następnik

tree succesor (x);

if right (x) <>nil then

return tree minimum (right(x))

else

begin

y:=parent(x)

while x=right(y) do

begin

x:=y

y:=parent(y)

end;

return y

end;

Poprzednik

tree predecessor (x)

if left (x) <>nil then

return tree maximum (left(x))

else

begin

y:=parent(x)

while x=left(y)

do

begin

x:=y

y:=parent (y)

end

return y

end

Dodawanie elementu

tree-insert(T,z)

y:=nil

x:=root (T)

while x<>nil do

y:=x

if key (z) < key (x) then

x:=left(x)

else

x:=right(x)

parent(z):=y

if y=nil then

root(T):=z

else

if key (z)<key (y) then

left(y):=z

else

right (y):=z

Usuwanie elementu

if (left(z)=nil) or (right(z)=nil) then

y:=z

else y:=pred (z)

if left (y) <> nil then

x:= left (y)

else

x:=right (y)

if x<>nil then

parent (x):=parent (y)

if parent (y) <> nil then

begin

if y=left (parent(y)) then

left (parent(y)):= x

else

right (parent (y)):=x

else

root(T):=x

if y<>z then

key (z):=key(y)

---