curs10.txt

STRUCTURI DE DATE SI ALGORITMI

                                       Curs 10


Coada cu prioritati

Este o structura de date pentru care sunt definite urmatoarele operatii:
insert (S,a)- insereaza un atom 宯 structura,
remove (S) - extrage din structura atomul cu cheia cea mai mare.
O coada cu prioritati poate fi implementata printr-o lista. Implementarea cozii
cu prioritati prin lista permite definirea operatiilor insert si remove, 宯
cazul cel mai bun, una este de complexitate O(1) si cealalta este de
complexitate O(n).
Implementarea cozii cu prioritati prin heap face o echilibrare cu complexitatea
urmatoare: una este de complexitate 0(log n) si cealalta de complexitate
0(log n).

Operatia de inserare                   /  \
heap:                                /      \
                                    /    50   \
				  /   /      \  \
                                 /  40         30 \
                               /   /   \       / \  \
                               /  33    37  12     2  \
                              /  /  \   /   _________\
                             /  10   15 7  | 42
                             --------------|

Acelasi arbore 宯 reprezentare implicita:


Operatiile insert si remove pentru arbori heap au o forma foarte simpla c僴d
utilizeaza reprezentarea implicita. Consideram, 宯 continuare, arbori heap 宯
reprezentare implicita.

Exemplu: un arbore cu ultimul nivel av僴d toate nodurile aliniate la st僴ga:

Inseram valoarea 42  se adauga nodul la un nivel incomplet;
In reprezentarea implicita se adauga nodul la sf價sit.

insert:

1) In reprezentarea implicita:  V [N + 1] = a
                                N = N + 1
In continuare reorganizam structura arborelui astfel 宯c僼  sa-si pastreze
structura de heap.
2) Se utilizeaza interschimbarile. Comparatii:
        Iau 2 indici:   child = N  si 
                        parent = [N/2]
        (宯 cazul nostru N = 11  si  [N/2] = 5)
        Comparam V[child] cu V[parent]
        Interschimbare daca V[child] nu este mai mic dec僼 V[parent](se schimb
42 cu 37)
3)Inaintare 宯 sus:     child  = parent
                        parent = [child/2]
4) Se reia pasul 2) p僴a c僴d nu se mai face interschimbarea.
Structura S este un arbore heap. El se afla 宯 reprezentare implicita 宯 2
informatii:
        V  vector
        N dimensiune
Operatia insert:

insert(V, N, a)  // V  vectorul ce contine reprezentarea
		 // implicita a heapu-lui;
                 // N  numarul de noduri din heap,
                 // ambele sunt plasate 
                 // prin referinta (functia insert
                 // le poate modifica); 
                 // a  atomul de inserat;
{ 
	N = N+1
	V[N] = a
	child = N
	parent = [N/2]
		while   | parent<=1 do
			|  if key(V [child]) > key(V [parent]) then
			|  interchange (V [child],V [parent])
			|	| child = parent
			|	|_ parent = [child/2]
			|_ else	break // parasim bucla  parent = 0 
}
Operatia remove:
                                 50
			       /    \
                             45      43
                           /   \    /   \
                         33    40 40     20
                       /   \    /  \        \
                      10    15 7   37        39

 se scoate elementul cel mai mare care este radacina heap-ului; se initializeaza
cei 2 indici;
 se reorganizeaza structura arborilor: se ia ultimul nod de pe nivelul incomplet
si-l aduc 宯 nodul-radacina, si aceasta valoare va fi retrogradata p宯a c僴d
structura heap-ului este realizata.
                                 parent
conditia de heap:                /   \
                             lchild  rchild
parent = max(parent, lchild, rchild).
  Exista trei cazuri:
1. conditia este 宯deplinita deodata;
2. max este 宯 st僴ga  retrogradarea se face 宯 st僴ga;
3. max este 宯 dreapta  retrogradarea se face 宯 dreapta.

remove(V, N)
{
        a= V[1]
        N[1]= V[N]
        N= N-1
        parent= 1
        child= 2
        while child <= N    do
                | if child+1  N and key(V[child+1]) >
                |  > key(V[child]) then
                |                  child= child+1
                |  if key(V[parent]) < key(V[child]) then 
                |       | interchange(V[parent], V[child])
                |       | parent= child
                |       |_ child= 2*parent
                |  else break
		|_ return(a)
}

Complexitatea celor doua operatii insert si remove:
In cazul cel mai defavorabil se parcurge o ramura care leaga radacina de un nod
terminal. La insert avem o comparatie, iar la remove avem doua comparatii.
Rezulta, complexitatea este data de ad僴cimea arborelui. Daca N este numarul
de noduri din arbore, 2k  N  2k+1 , si ad僴cimea arborelui este k+1.

                    (2 la k)-1 < N<=(2 la k+1)-1 => k =  [log2N]

                         |            |
                         |            |
                         |            |
                   nr. de noduri     nr. de noduri 
                   ale arborelui     ale arborelui 
                   complet de        complet de 
                   ad僴cime k        ad僴cime k+1

log2N <=> log in baza 2 din N
k <= log2N  <  k + 1 => ad僴cimea arborelui este k =  [log2N].
Deci complexitatea este O(log N).
A doua aplicatie a heap-urilor este algoritmul Heap_Sort.

Algoritmul Heap_Sort
Heap_Sort(V, n)
{
        heap_gen(V, n)  N = n
        for i = n downto 2 step -1   do
                | N = i
                |_ V[i] = remove(V, N)
}

Aceasta procedura sorteaza un vector V cu N elemente: transforma vectorul V
宯tr-un heap si sorteaza prin extrageri succesive din acel heap.

Procedura Heap_Sort prin inserari repetate

heap_sort
{
		 N = 1  //se considera pentru 宯ceput un
                        // heap cu un singur
                        //element, dupa care toate celelalte
			// elemente vor fi
                        //inserate 宯 acest heap
          for  i = 2  to  n  do
                 insert(V, N, V[i])
}
Studiul complexitatii
Observatii:
 Se fac mai multe operatii insert 宯 heap-uri  a caror dimensiune creste de la
1 la N;
 Se fac n-1 operatii insert 宯 heap-uri cu dimensiunea N<=n
Rezulta complexitatea acestor operatii nu depaseste O(nlog n). Facem un studiu
pentru a vedea daca nu cumva ea este mai mica dec僼 O(nlog n).
Cazul cel mai defavorabil este situatia 宯 care la fiecare inserare se parcurge
o ramura completa. De fiecare data inserarea unui element se face adaug僴d un
nod la ultimul nivel. Pentru nivelul 2 sunt doua noduri. La inserarea lor se
va face cel mult o retrogradare (comparatie).
Pe ultimul exemplu de arbore, avem:
nivelul 2               :  2 noduri  1 comparatie
nivelul                 :  4 noduri  2 comparatii
nivelul 4               :  8 noduri  3 comparatii
--------------------------------------------------
nivelul i               :  2i-1 noduri  i-1 comparatii

Consider僴d un arbore complet (nivel complet)  N = 2k - 1  numarul total de
comparatii pentru toate nodurile este T(n) de la nivelul 2 la nivelul k.
Vom calcula:

Sa aratam:	
cu tehnica	.	Asadar:

Rezulta:		
iar:		 ,
din		
Rezulta:		
			------------------------
			  termen dominant  

Fac僴du-se majorari, rezulta complexitatea O(nlog n).
Prezentam acum alta strategie de obtinere a heap_gen cu o complexitate mai
buna:
Construim heap-ul de jos 宯 sus (de la dreapta spre st僴ga). Cele mai multe
noduri sunt la baza, doar nodurile din v價f parcurg drumul cel mai lung.

Elementele V[i+1,N] 宯deplinesc conditia de structura  a heap-ului:
oricare ar fi j >i avem:V[j] > V[2*j] , daca 2*j<=N
                        V[j] > V[2*j +1] , daca 2*j + 1 <= N
Algoritmul consta 宯 adaugarea elementului V[i] la structura heap-ului. El va
fi retrogradat la baza heap-ului (prelucrare prin retrogradare):

retrogradare(V, N, i)
{
        parent = i
        child = 2*i  // fiu st僴ga al lui i
        while child  N    do
                | if child+1<=N and 
		|     key(V[child+1]) > key(V[child]) then
                |                child = child+1
		|  if key(V[parent]) < key(V[child]) then
                |       | interchange(V[parent], V[child])
                |       |  parent = child
		|       |_ child = 2*parent
                |_ else  break
}

In aceasta situatie, vom avea:

heap_gen
{
    for i = [N/2] downto  1  step  -1   do
                    retrogradare(V, n, i)
}

Complexitatea acestei operatii
(2k <=> 2 la puterea k;oricare ar fi k)
Fie un arbore complet cu n = 2k - 1. Cazul cel mai defavorabil este situatia
宯 care la fiecare retrogradare se parcurg toate nivelele:
nivel k                 : nu se fac operatii
nivel k-1               : 2k-2 noduri o operatie de comparatie
nivel k-2		: 2k-3 noduri		2 operatii
------------------------------------------------------------------
nivel i		: 2i-1 noduri		k-i operatii
-------------------------------------------------------------------
nivel 2		: 21 noduri		k-2 operatii
nivel 1		: 20 noduri		k-1 operatii
Se aduna, si rezulta:		
Tehnica de calcul este aceeasi:	

Rezulta:				
				
 					-------
					termen dominant

Rezulta complexitatea este O(n). Compar僴d cu varianta anterioara,
宯 aceasta varianta (cu heap-ul la baza) am c僺tigat un ordin de complexitate.
Rezulta, complexitatea algoritmului Heap_Sort este determinata de functiile
remove ce nu pot fi aduse la mai putin de complexitate O(log n). Rezulta:
                Heap_Sort = O(n) + O(n鷏og n)
				---------------
			termen ce determina complexitatea

	  Rezulta complexitatea alg. Heap_Sort = O(n鷏og n)