7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 1/10
VII. Tipul Abstract de Date Coadă Prioritară.
Pentru a compara elementele unei colecţii se utilizează o parte din fiecare element numită cheie.Cheile sunt comparabile, folosind o regulă de comparaţie de tipul ≤. Aceasta determină o relaţie
de ordine totală, caracterizată prin:• reflexivitate: k k
• antisimetrie: k1 k2 ∩ k2 k1 ⇒
k1 = k2
• tranzitivitate: k1 k2 ∩ k2 k3 ⇒ k1 k3
O coadă prioritară este o colecţie în care fiecare element are asociată o cheie sau prioritate! caredetermină ordinea în care se plasează elementele în colecţie în cursul operaţiei de inserare. Celmai prioritar element va fi plasat în v"rful cozii #i va fi primul element extras din colecţie.$n element al cozii prioritare va fi constituit dintr%o pereche cheie, valoare!.Operaţiile principale specifice cozii prioritare sunt:
% inserarea unei perechi (k, v) în coadă într%o poziţie corespunzătoare priorităţii lui% #ter&erea elementului cu cheie minimă cel mai prioritar! din coada prioritară
Cozile prioritare sunt utilizate în sistemele de operare la planificarea proceselor, a operaţiilor de
intrare'ie#ire, în problema selecţiei, în simularea evenimentelor, etc.Specificare TAD Coadă Prioritară
% (omenii: PQ ) Coadă Prioritară Elem (int x val) = tip elemente coadă prioritarăint = prioritate val = tip valoare asociată
% *uncţii: % creare coadă prioritară vidă new : PQ
% inspectarea celui mai prioritar element min : PQ Elem
% #ter&erea celui mai prioritar element delmin : PQ Elem
% inserarea unui element în coada prioritară insert : PQ × int × val PQ
% modificarea cheii unui element chpr : PQ × Elem × int PQ
% test coadă prioritară vidă empty: PQ int
% Axiome:+. PQ new(). min(insert(new(), x))=x-. delmin(insert(new(), x))=new(). min(insert(insert(PQ,y),x))=i pri(x) ! pri(min(insert(PQ,y)))
x else
min(insert(PQ,y))/. delmin(insert(insert(PQ,y),x))=i pri(x)!pri(min(insert(PQ,y)))
insert(PQ,y)
elseinsert(delmin(insert(PQ,y),x)
O coadă prioritară poate fi implementată naiv folosind:a! o listă nesortată 0 inserarea se face întotdeauna la începutul listei în "(1), dar #ter&erea presupune în prealabil &ăsirea elementului cel mai prioritar în "(n). b! o listă sortată 0 inserarea se face în "(n), păstr"nd relaţia de ordine dintre elemente, iar#ter&erea se face în "(1) de la un capăt al listei
+
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 2/10
c! un arbore binar de căutare 0 inserarea #i #ter&erea se fac în "(l#$ n), dar arborele trebuiefrecvent reechilibrat, deoarece #ter&erea se face mereu din acela#i loc.
O implementare eficientă a cozii prioritare cu heapuri binare asi&ură complexitatea "(l#$ n)at"t pentru inserare, c"t #i pentru #ter&ere. 1umeroase aplicaţii impun determinarea eficientă a poziţiei fiecărui element din coada
prioritară. 2n acest scop vom asocia fiecărui element un locator 0 o valoare întrea&ă,reprezent"nd poziţia pe care o ocupă elementul în coada prioritară. Orice deplasare aelementului în coada prioritară va conduce la modificarea locatorului.
Interfaţă TAD Coadă Prioritară
PQ PQ%&ew()' creere c#ada pri#ritara vidaint PQ%Empty (PQ h)' test c#ada pri#ritara vidaint PQ%*ll (PQ h)' test c#ada pri#ritara plinaElem PQ%+in(PQ h)' preia element*l c* cheia minimav#id PQ%el+in(PQ h)' ster$e element*l c* cheia minimaint PQ%-nsert (PQ h, int k, v#id .v)' inserea/0 (k,v) in cpint PQ%hPr(PQ h,int p,int k)' schim0 pri#ritatea element*l*i
din p#/i4ia p la val#area kint PQ%5i/e(PQ h)' nrelemente c#ada pri#ritara
Exemple.Sortare folosind o coadă prioritară.
% elementele listei nesortate se scot din listă #i se introduc într%o coadă prioritară.% se scot elementele din coada prioritară #i se inserează în lista sortată
PQ_SORT(L)Intrare: L-lista cu elemente nesortateIeşire: L-lista cu elemente sortate
PQ = new()while ! emt(L) e = remo"e(L# $e%in(L)) insert(PQ# e# e)
while ! emt(PQ) e = &elmin(PQ) insert(L# en&(L))
Sortarea prin selecţie este o variantă a sortării cu coadă prioritară implementată cu listă nesortată.Al&oritmul de sortare necesită n #ter&eri cu complexitate: '*n = O(n) #i n inserări cucomplexitate n+O(')=O(n).
Sortarea prin inserţie este tot o variantă a sortării cu coadă prioritară, implementată cu listă
sortată. 2n acest caz operaţiile de inserare au complexitate '*n = O(n
) iar #ter&erile,n+O(')=O(n).
O implementare mai eficientă a cozii prioritare ar conduce la performanţe mai bune aleal&oritmului de sortare. 3mplementarea cu heapuri a cozii prioritare cu complexitate O(lo% n),at"t pentru inserare c"t #i pentru #ter&ere!, conduce la cunoscuta metodă de sortare cu heapuri 0heapsort.
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 3/10
Heapuri. arbori parţial ordonaţi!
Definiţii "i terminolo#ie.
$n arbore binar perfect sau plin! are pe fiecare nivel h un număr maxim de noduri 2h. 1umărultotal de noduri n, corespunz"nd unei înălţimi h a arborelui perfect este:n=162662h=2h6171
(intre toţi arborii cu n noduri, arborele binar plin are înălţimea minimă:h=l#$2(n61)71=l#$2n
2ntr%un arbore binar complet :
0. fiecare nivel i, except"nd ultimul are 2i noduri+. nodurile de pe ultimul nivel sunt aliniate la st"n&a
1umărul de noduri, pentru un arbore binar complet de înălţime h este: 2h n 2h6171 de undeh= l#$2n
$n arbore binar complet poate fi reprezentat în mod eficient printr%un vector fără a folosi pointeri!, în care elementele vectorului sunt cheile din noduri, iar indicii elementelor corespundnumerotării nodurilor pe niveluri în lăr&ime!. 2n acest caz, le&ăturile unui nod la succesori #i predecesor se stabilesc astfel:
Aceste relaţii corespund indexării în vector de la 45dacă prima poziţie nu este folosită rădăcinaeste indexată cu +!, relaţiile sunt:
tata(i)=i2,i*%st8n$a(i)=2.i,i*%dreapta(i)=2.i61
h
h
i)indexul elementului în vector
6i7+)index fiu st"n&a 6i7)index fiu dreapta
i%+!')index părinte, dacă i84
-
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 4/10
9ste posibil să reprezentăm printr%un vector #i un arbore binar care nu este complet. Pentru astabili în vector relaţiile de tip tată 0 fiu între elemente, acestea vor trebui plasate în poziţiile pecare le%ar ocupa în arborele binar complet, adică vectorul va prezenta &oluri poziţii libere!corespunzătoare nodurilor lipsă din arborele binar complet. Astfel arborelui binar:
2i corespunde vectorul:
(acă vectorul are n elemente, succesorul st"n& al elementului cu indexul i există dacă 2.i61!nde asemenea tatăl nu este definit dacă i=9!.
$nheap
sauarbore
parţial ordonat
saumovilă
!0. are o proprietate de structură, fiind un arbore binar complet
1. are o proprietate de ordine între cheia nodului părinte #i cheile nodurilor fii.enţionăm că între cheile fiilor unui nod fraţi! nu există nici o relaţie de ordine.2ntr%un heap maxim o cheia dintr%un nod este mai mare dec"t cheile din nodurile fii.o cheia din nodul rădăcină este cheia maximă din heap.
o Orice cale de la rădăcină la o frunză este o secvenţă descrescătoare de chei. 3n mod asemănător se define#te un heap minim.
O definire recursivă a unui heap maxim este : un arbore binar complet care. fie este vid-. fie are cheia din rădăcină mai mare dec"t cheile din succesorii direcţi ai rădăcinii #i. subarborii oricărui nod sunt heapuri3ntr%un heap:o operaţiile de inserare #i de ştergere se realizează foarte eficient în Olo& n!!.o o cale de la rădăcină la o frunză este o secvenţă ordonată de chei.
2ntr%un heap minim maxim!, un nod care nu respectă relaţia de ordine a heapului:
+
=
< +- +
5 8 12 3 9 4 5 8
0 1 2 3 4 5 6 7 8 9 1011 12 13 14
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 5/10
5. migrează în sus filtrare sus, sift%up, bubble%up! dacă este mai mic'mare dec"t predecesorul. (eplasarea se opre#te în momentul în care nodul a>un&e pe un nivel la care relaţiade ordine a heapului este respectată. 1odul poate mi&ra p"nă în rădăcină nivel 4!
6. migrează în jos filtrare >os, sift%do?n, bubble%do?n! dacă este mai mare'mic dec"tunul dintre succesorii direcţi. (eplasarea se opre#te în momentul în care nodul a>un&e pe un nivella care relaţia de ordine a heapului este respectată. 1odul poate mi&ra p"nă într%o frunză.
*uncţia iltr*#s() va fi definită cu parametri: heapul h, poziţia iniţială în heap aelementului care coboară p, numărul de elemente din heap n nu am folosit valoarea h7;n,deoarece în cazul sortării prin metoda heapurilor, dimensiunea heapului se schimbă! #i funcţia decomparaţie a priorităţilor.
2n interfaţă se declară o structură nespecificată #i un pointer opac la ea:
str*ct heap'typede str*ct heap .PQ'
$n heap va fi definit în secţiunea de implementare ca o structură ce conţine:
onumărul de elemente n,
o dimensiunea maximă p"nă la care se poate extinde heapul +<
o un vector a cu elemente de orice tip .
str*ct heap> int n' int +<' v#id ..a'?'
v#id iltr*#s(PQ h, int p, int n, P c#mp)> int i*' v#id .t = h7;a@pA'
#r( ' 2.p61 ! n' p=i*)> i* = 2.p61' i(i*61 ! n BB c#mp(h7;a@i*61A, h7;a@i*A) ! 9) i*66' i(c#mp(t, h7;a@i*A) != 9) reak' else h7;a@pA = h7;a@i*A' ?' h7;a@pA = t'?
v#id iltr*5*s(PQ h, int i, P c#mp)>
v#id .x = h7;a@iA' #r( ' i;9 BB c#mp(x, h7;a@(i71)2)!9' i=(i71)2A) h7;a@iA=h7;a@(i71)2A'
h7;a@iA = x'?
/
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 6/10
Transformarea unui tablou $ntr%un &eap.
Prin mi&rarea unui sin&ur element în >os sau în sus!, arborele binar complet nu se transformă înheap.
@ransformarea în heap a unui arbore binar complet se face prin eventuala! mi&rare în >os a
tuturor rădăcinilor de heapuri. 1odurile frunze îndeplinesc relaţia de ordine a heapului, deci nu semai verifică.
Primul nod verificat va fi părintele ultimului nod n71!, adică cel cu indexul (n72)2iar ultimul va fi rădăcina.
v#id rheap(PQ h, P c#mp)> int crt' #r(crt = h7;((n72)2)' crt;=9' crt77) iltr*#s(h, crt, h7;n, c#mp)'?
Complexitatea filtrării în sus sau în >os! este dată de lun&imea traseului elementului p"nă lafixarea lui pe un nivel.Aceasta nu poate depă#i înălţimea arborelui deci
"(h)="(l#$ n)@ransformarea unui vector într%un heap presupune eventuala mi&rare a tuturor nodurilor interne. 1umărul acestora este n2 deci complexitatea este "(nl#$ n).O estimare mai exactă observă că într%un heap există cel mult
n2h61 noduri de înălţime h.
(eci:
n"2
hn"h"
2
n nl#$
9hh
nl#$
9h1h
=
=
∑
=
deoarece
1x,x1
1x
9i
i<
=
∞
=
∞
=
=
9i2
1i
x1
1ix
∞
=
=
1i2
i
x1
xix
2
2
11
2
1
2
i
1i2i
=
=
∞
=
Sortare prin metoda &eapurilor
eprezintă o metodă foarte eficientă de sortare cu complexitatea "(nl#$2n).Pentru a folosi @A( heap binar, definit mai sus, vom plasa tabloul de sortat în heap, iar dupăsortare vom extra&e tabloul din heap.
B. ectorul de sortat este transformat în prealabil într%un heap. om considera vectorulseparat în două părţi, una nesortată, constituită iniţial din tot vectorul #i una de>a sortată, iniţialvidă.
;. 9lementul maxim se află în rădăcină, de unde este trecut în zona sortată, prin schimbcu ultimul element din heap.
=
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 7/10
Deapul, deci zona nesortată se restr"n&e cu un element, în timp ce zona sortată se extinde.Prin plasarea ultimului element în rădăcină, relaţia de ordine a heapului este încălcată, #i vomrestabili heapul prin filtrarea în >os a elementului din rădăcină.
v#id heaps#rt(PQ h, P c#mp)> v#id .el'
int i' rheap(h, c#mp)' #r(int i=h7;n71' i;9' i77)> swap(h7;a@9A,h7;a@iA)' iltr*#s(h, 9, i, c#mp)' ??
$n arbore parţial ordonat are înălţimea k=l#$2n. Ea transformarea tabloului în heap suntnecesare n2 filtrări >os, fiecare necesit"nd cel mult k comparaţii. 2n ciclu se mai fac n71 filtrări >os, deci:
& = k.n2 6 k.(n71) = k.(3.n271) = "(kn) = "(nl#$2n)
Deapurile se implementează mult mai u#or dec"t arborii care necersită #i echilibrare!.Deapurile nu necesită spaţiu pentru pointeri.
etoda de sortare dezvoltată este foarte eficientă.
Implementare TAD Coadă Prioritară cu &eapuri binare.
$n element al cozii prioritare va fi un triplet cheie, informaţie, locator!, cheia sau prioritatea! #i poziţia în coada prioritară fiind între&i, iar informaţia asociată cheii, put"nd fi de orice tip.
typede str*ct elem> int key' v#id .val'
int l#c'? .Elem'
PQ PQ%&ew ()> PQ h=(PQ)mall#c(si/e#(str*ct heap))' h7;n=9' h7;+<=199' h7;a=(Elem.)mall#c(h7;+<.si/e#(Elem))' ret*rn h'?
int PQ%5i/e (PQ h)>ret*rn h7;n'?
int PQ%Empty (PQ h)>ret*rn h7;n==9'?int PQ%*ll (PQ h)> ret*rn h7;n==h7;+<'?Elem PQ%+in(PQ h)>ret*rn h7;a@9A'?
B
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 8/10
5 A 0
10 B 2
7 C 1
21 K 5
15 H 4
12 D 3
6
100
a
n
MAX
5 A 0
7 C 110 B 2
12 D 321 K 5 15 H 4
0
1 2
3 4 5
3n operaţiile de filtrare se fac următoarele modificări:• se actualizează locatorii elementelor deplasate• dispare funcţia de comparaţie este înlocuită cu operatorul de comparaţie• funcţiile întorc poziţia finală pe care o ocupă în coada prioritară elementul deplasat
int iltr*#s(PQ h, int p, int n)> int i*' Elem t = h7;a@pA' #r( ' 2.p61 ! n' p=i*)> i* = 2.p61' i(i*61 ! n BB h7;a@i*61A7;key ! h7;a@i*A7;key)
i*66' i(t7;key != h7;a@i*A7;key) reak' h7;a@i*A7;l#c77' t7;l#c66' h7;a@pA = h7;a@i*A' ?' h7;a@pA = t' ret*rn t7;l#c'?
;
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 9/10
int iltr*5*s(PQ h, int p)> Elem t = h7;a@pA' int tata' while(p ; 9)>
tata = (p71)2' i(t7;key ;= h7;a@tataA7;key) reak' h7;a@tataA7;l#c66' t7;l#c77' h7;a@pA=h7;a@tataA' ? h7;a@pA = t' ret*rn t7;l#c'?
Ea #ter&erea elementului din v"rful heapului în locul primului element rădăcină! se pune ultimulelement din heap #i se scade numărul de elemente. Plasarea ultimului element în v"rful heapului poate strica relaţia de ordine a heapului. Pentru a o restabili, se interschimbă elementul din v"rf
cu cel mai mic dintre fii. Procesul de cobor"re în heap poate continua p"nă c"nd se a>un&e într%o poziţie în care proprietatea de ordine a heapului este respectată sau p"nă se a>un&e într%o frunză!.
v#id PQ%el+in(PQ h)> assert(CPQ%Empty (h))' h7;a@9A = h7;a@h7;n 7 1A' h7;n77' iltr*#s(h, 9, h7;n)'?
Pentru a insera un element în heap, acesta se adau&ă la sf"r#itul heapului #i se cre#te numărul deelemente. (acă ordinea în heap este respectată elementul adău&at nu este mai mic dec"t părintele! operaţia se încheie. 2n caz contrar elementul introdus comută cu părintele, ridic"ndu%se
în heap. (rumul său poate continua spre rădăcină, c"t timp ordinea nu este respectată.int PQ%-nsert (PQ h, int k, v#id .v)> assert(CD%*ll (h))' Elem e = (Elem)mall#c(si/e# str*ct elem)' e7;key = k' e7;val = v' e7;l#c = h7;n' int n=66h7;n' h7;a@h7;n71A=e' ret*rn iltr*5*s(h, n)'?
2n operaţiile cu &rafuri al&oritmul (i>Fstra! prioritatea unui element se poate modifica, ceea ceconduce la rea#ezarea lui în coada prioritară.
(acă implementăm coada prioritară printr%un heap minim, cre#terea priorităţii elementului din poziţia p la valoarea k determină ridicarea în heap a elementului, deci o filtrare în sus, în timp ceo scădere a priorităţii determină o cobor"re în heap, deci o filtrare în >os. *uncţia întoarce noua poziţie pe care o ocupă elementul deplasat în coada prioritară.
int PQ%hPri(PQ h, int p, int k)> EE+ temp=h7;a@pA'
<
7/18/2019 C8-Tipul Abstract de Date Coada Prioritara
http://slidepdf.com/reader/full/c8-tipul-abstract-de-date-coada-prioritara 10/10
h7;a@pA7;key = k' i(k ! temp7;key) ret*rn iltr*5*s(h, p)' else ret*rn iltr*#s(h, p, h7;n)'?
Aplicaţii ale co'ilor prioritare.
Selecţia celui de%al p%lea element.
Soluţia (
9. se crează un heap minim cu cele n elemente în "(n)!
10. se extra& p elemente în "(pl#$ n)!
Soluţia )
11. se crează un heap minim cu primele p elemente
+. pentru celelalte elementedacă elem;min se scoate minimul #i se pune elem în heap în "(nl#$ p) dar folose#te unheap cu numai p elemente.
Probleme propuse.
("ndu%se un tablou de n între&i distincţi, scrieţi o funcţie cu complexitatea "(n6p l#$ n),care determină cel de%al p%lea cel mai mare între& din tablou.
@ransformaţi într%un heap maxim tabloul
O &rupă conţine n studenţi, precizaţi prin nume #i calificativ. Primilor √n studenţi li s%a dat nota
+4. Gtabiliţi care sunt ace#tia. *olosiţi un al&oritm cu complexitate mai mică dec"t O(n lo%n)adică nu se admite soluţia sortare descrescătoare după note #i selectarea primilor √n
Gcrieţi un al&oritm care stabile#te în O(n lo% n), dacă într%un vector cu n componente între&i,există între&i , #i astfel ca ,=, în care este dat.*ie . un heap maxim, cu n elemente.Gcrieţi un al&oritm av"nd complexitatea mai mică dec"tO(n), care modifică valoarea unui element de la "' la ".
puncte@ransformaţi secvenţa: /, 4, /, B, -=, ;4, +/, /4, +44, +4, =4, 4.
a! într%un heap maxim b! într%un heap minm
@ransformaţi într%un heap minim #i într%un heap maxim secvenţa:/0# '1# 02# 3# '22# /# 42# '# 12# /25
@ransformaţi într%un heap minim #i într%un heap maxim secvenţa:31# 6# '2# 12# 1# 37# 0# '22# 2# 32# '# '1
+4