Este o structura de date pentru care sunt definite urmatoarele operatii: insert (S,a)- insereaza un atom Œn structura, remove (S) - extrage din structura atomul cu cheia cea mai mare. t1d13do
O coada cu prioritati poate fi implementata printr-o lista. Implementarea cozii cu prioritati prin lista permite definirea operatiilor insert si remove, Œn 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 Œn reprezentare implicita:

Operatiile insert si remove pentru arbori heap au o forma foarte simpla cƒnd utilizeaza reprezentarea implicita. Consideram, Œn continuare, arbori heap Œn reprezentare implicita.

Exemplu: un arbore cu ultimul nivel avƒnd toate nodurile aliniate la stƒnga:

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

insert:

1) In reprezentarea implicita: V aN + 1i = a
N = N + 1
In continuare reorganizam structura arborelui astfel Œncƒt sa-si pastreze structura de heap.
2) Se utilizeaza interschimbarile. Comparatii:
Iau 2 indici: child = N si parent = aN/2i
(Œn cazul nostru N = 11 si aN/2i = 5)
Comparam Vachildi cu Vaparenti
Interschimbare daca Vachildi nu este mai mic decƒt Vaparenti(se schimb
42 cu 37)
3)Inaintare Œn sus: child = parent parent = achild/2i
4) Se reia pasul 2) pƒna cƒnd nu se mai face interschimbarea.
Structura S este un arbore heap. El se afla Œn reprezentare implicita Œn 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;
A
N = N+1
VaNi = a child = N parent = aN/2i
while | parent<=1 do
| if key(V achildi) > key(V aparenti) then
| interchange (V achildi,V aparenti)
| | child = parent
| |_ parent = achild/2i
|_ else break // parasim bucla parent = 0
S
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 Œn nodul-radacina, si aceasta valoare va fi retrogradata pŒna cƒnd structura heap-ului este realizata. parent conditia de heap: / \ lchild rchild parent = max(parent, lchild, rchild).
Exista trei cazuri:
1. conditia este Œndeplinita deodata;
2. max este Œn stƒnga retrogradarea se face Œn stƒnga;
3. max este Œn dreapta retrogradarea se face Œn dreapta.

remove(V, N)
A a= Va1i
Na1i= VaNi
N= N-1 parent= 1 child= 2
while child <= N do
| if child+1 N and key(Vachild+1i) >
| > key(Vachildi) then
| child= child+1
| if key(Vaparenti) < key(Vachildi) then
| | interchange(Vaparenti, Vachildi)
| | parent= child
| |_ child= 2*parent
| else break
|_ return(a)
S

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ƒncimea arborelui. Daca N este numarul de noduri din arbore, 2k N 2k+1 , si adƒncimea arborelui este k+1.

(2 la k)-1 < N<=(2 la k+1)-1 => k = alog2Ni

| |
| |
| | nr. de noduri nr. de noduri ale arborelui ale arborelui complet de complet de adƒncime k adƒncime k+1

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

Algoritmul Heap_Sort
Heap_Sort(V, n)
A heap_gen(V, n) N = n for i = n downto 2 step -1 do
| N = i
|_ Vaii = remove(V, N)
S

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

Procedura Heap_Sort prin inserari repetate

heap_sort
A
N = 1 //se considera pentru Œnceput un
// heap cu un singur
//element, dupa care toate celelalte
// elemente vor fi
//inserate Œn acest heap for i = 2 to n do insert(V, N, Vaii)
S
Studiul complexitatii
Observatii:
Se fac mai multe operatii insert Œn heap-uri a caror dimensiune creste de la
1 la N;
Se fac n-1 operatii insert Œn 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ƒt O(nlog n).
Cazul cel mai defavorabil este situatia Œn care la fiecare inserare se parcurge o ramura completa. De fiecare data inserarea unui element se face adaugƒnd 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ƒnd 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ƒndu-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 Œn sus (de la dreapta spre stƒnga). Cele mai multe noduri sunt la baza, doar nodurile din vƒrf parcurg drumul cel mai lung.

Elementele Vai+1,Ni Œndeplinesc conditia de structura a heap-ului: oricare ar fi j >i avem:Vaji > Va2*ji , daca 2*j<=N
Vaji > Va2*j +1i , daca 2*j + 1 <= N
Algoritmul consta Œn adaugarea elementului Vaii la structura heap-ului. El va fi retrogradat la baza heap-ului (prelucrare prin retrogradare):

retrogradare(V, N, i)
A parent = i child = 2*i // fiu stƒnga al lui i
while child N do
| if child+1<=N and
| key(Vachild+1i) > key(Vachildi) then
| child = child+1
| if key(Vaparenti) < key(Vachildi) then

| | interchange(Vaparenti, Vachildi)
| | parent = child
| |_ child = 2*parent
|_ else break
S

In aceasta situatie, vom avea:

heap_gen
A for i = aN/2i downto 1 step -1 do retrogradare(V, n, i)
S

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
Œn 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ƒnd cu varianta anterioara,
Œn aceasta varianta (cu heap-ul la baza) am cƒstigat 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úlog n)
-------------- termen ce determina complexitatea

Rezulta complexitatea alg. Heap_Sort = O(núlog n)

Curs 10

Coada cu prioritati

Este o structura de date pentru care sunt definite urmatoarele operatii: insert (S,a)- insereaza un atom Œn 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, Œn 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 Œn reprezentare implicita:

Operatiile insert si remove pentru arbori heap au o forma foarte simpla cƒnd utilizeaza reprezentarea implicita. Consideram, Œn continuare, arbori heap Œn reprezentare implicita.

Exemplu: un arbore cu ultimul nivel avƒnd toate nodurile aliniate la stƒnga:

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

insert:

1) In reprezentarea implicita: V aN + 1i = a
N = N + 1
In continuare reorganizam structura arborelui astfel Œncƒt sa-si pastreze structura de heap.
2) Se utilizeaza interschimbarile. Comparatii:
Iau 2 indici: child = N si parent = aN/2i
(Œn cazul nostru N = 11 si aN/2i = 5)
Comparam Vachildi cu Vaparenti
Interschimbare daca Vachildi nu este mai mic decƒt Vaparenti(se schimb
42 cu 37)
3)Inaintare Œn sus: child = parent parent = achild/2i
4) Se reia pasul 2) pƒna cƒnd nu se mai face interschimbarea.
Structura S este un arbore heap. El se afla Œn reprezentare implicita Œn 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;
A
N = N+1
VaNi = a child = N parent = aN/2i
while | parent<=1 do
| if key(V achildi) > key(V aparenti) then
| interchange (V achildi,V aparenti)
| | child = parent
| |_ parent = achild/2i
|_ else break // parasim bucla parent = 0
S
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 Œn nodul-radacina, si aceasta valoare va fi retrogradata pŒna cƒnd structura heap-ului este realizata. parent conditia de heap: / \ lchild rchild parent = max(parent, lchild, rchild).
Exista trei cazuri:
1. conditia este Œndeplinita deodata;
2. max este Œn stƒnga retrogradarea se face Œn stƒnga;
3. max este Œn dreapta retrogradarea se face Œn dreapta.

remove(V, N)
A a= Va1i
Na1i= VaNi
N= N-1 parent= 1 child= 2
while child <= N do
| if child+1 N and key(Vachild+1i) >
| > key(Vachildi) then
| child= child+1
| if key(Vaparenti) < key(Vachildi) then
| | interchange(Vaparenti, Vachildi)

| | parent= child
| |_ child= 2*parent
| else break
|_ return(a)
S

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ƒncimea arborelui. Daca N este numarul de noduri din arbore, 2k N 2k+1 , si adƒncimea arborelui este k+1.

(2 la k)-1 < N<=(2 la k+1)-1 => k = alog2Ni

| |
| |
| | nr. de noduri nr. de noduri ale arborelui ale arborelui complet de complet de adƒncime k adƒncime k+1

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

Algoritmul Heap_Sort
Heap_Sort(V, n)
A heap_gen(V, n) N = n for i = n downto 2 step -1 do
| N = i
|_ Vaii = remove(V, N)
S

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

Procedura Heap_Sort prin inserari repetate

heap_sort
A
N = 1 //se considera pentru Œnceput un
// heap cu un singur
//element, dupa care toate celelalte
// elemente vor fi
//inserate Œn acest heap for i = 2 to n do insert(V, N, Vaii)
S
Studiul complexitatii
Observatii:
Se fac mai multe operatii insert Œn heap-uri a caror dimensiune creste de la
1 la N;
Se fac n-1 operatii insert Œn 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ƒt O(nlog n).
Cazul cel mai defavorabil este situatia Œn care la fiecare inserare se parcurge o ramura completa. De fiecare data inserarea unui element se face adaugƒnd 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ƒnd 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ƒndu-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 Œn sus (de la dreapta spre stƒnga). Cele mai multe noduri sunt la baza, doar nodurile din vƒrf parcurg drumul cel mai lung.

Elementele Vai+1,Ni Œndeplinesc conditia de structura a heap-ului: oricare ar fi j >i avem:Vaji > Va2*ji , daca 2*j<=N
Vaji > Va2*j +1i , daca 2*j + 1 <= N
Algoritmul consta Œn adaugarea elementului Vaii la structura heap-ului. El va fi retrogradat la baza heap-ului (prelucrare prin retrogradare):

retrogradare(V, N, i)
A parent = i child = 2*i // fiu stƒnga al lui i
while child N do
| if child+1<=N and
| key(Vachild+1i) > key(Vachildi) then
| child = child+1
| if key(Vaparenti) < key(Vachildi) then
| | interchange(Vaparenti, Vachildi)
| | parent = child
| |_ child = 2*parent
|_ else break
S

In aceasta situatie, vom avea:

heap_gen
A for i = aN/2i downto 1 step -1 do retrogradare(V, n, i)
S

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
Œn 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ƒnd cu varianta anterioara,
Œn aceasta varianta (cu heap-ul la baza) am cƒstigat 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úlog n)
-------------- termen ce determina complexitatea

Rezulta complexitatea alg. Heap_Sort = O(núlog n)