Coadă prioritară

În teoria cozii , o coadă prioritară este o structură de date abstractă, similară cu o coadă sau o stivă, dar diferită de acestea prin faptul că fiecare element inserat în coadă are propria „prioritate”. Într-o coadă de prioritate, fiecare element cu prioritate mai mare este inserat înaintea unui element cu prioritate mai mică. În special, elementul cu cea mai mare prioritate se află în capul cozii, cel cu cea mai mică prioritate va fi găsit în coadă.

Operațiuni

Cozile prioritare trebuie să susțină în mod necesar aceste operațiuni:

insert (element e, cheia k): Această operație introduce elementul e în coadă în funcție de prioritatea definită de cheia k.
findMin (): Această operațiune returnează cel mai mic element de coadă cu prioritate, fără a-l șterge.
removeMin (): Această operațiune elimină elementul de coadă cu cea mai mică prioritate.
findMax (): Această operație returnează elementul de coadă cu cea mai mare prioritate, fără a-l șterge.
removeMax (): Această operație returnează elementul de coadă cu cea mai mare prioritate.

Implementare

Heapul binar este adesea folosit pentru a implementa o coadă prioritară, deoarece această structură permite inserarea și ștergerea într-un timp de O (logn) în cel mai rău caz. De asemenea, este posibil să utilizați grămezi binomiale sau grămezi Fibonacci pentru a face anumite operații mai eficiente. ^[1] Datorită implementării naturale a cozilor prioritare cu grămezi, acestea sunt adesea menționate în literatură ca grămadă inversată . Prin grămadă inversată înțelegem o grămadă care are cel mai mic element al copacului la rădăcină și nu cel mai mare și în care fiecare copil este mai mare decât tatăl, adică contrar unei grămezi standard.

Aplicații

Cozile prioritare sunt utilizate pe scară largă în tehnologia informației și, în general, în procesarea datelor (inclusiv telecomunicații și circuite electronice digitale) pentru a efectua operațiuni complexe, cum ar fi:

sortarea elementelor pe baza priorității acestora
optimizări în ceea ce privește accesul la resursele partajate, în special în cazul acceselor concurente și al congestiei
gestionarea activităților programate
algoritmi de căutare euristică

Relația dintre coada de prioritate și algoritmii de căutare

O coadă prioritară este adesea cuplată cu algoritmi de căutare. Tabelul următor indică cea mai bună implementare și diferitele costuri pentru fiecare algoritm:

Algoritm	Implementare cu cozi prioritare	Cel mai bun caz	Carcasă medie	Cel mai rău caz
Smoothsort	Mormanul lui Leonardo	$n$ ${\ displaystyle n}$ $n$	$nlog(n)$ ${\ displaystyle nlog (n)}$ ${\ displaystyle nlog (n)}$	$nlog(n)$ ${\ displaystyle nlog (n)}$ ${\ displaystyle nlog (n)}$
Sortare selecție	Array nu este sortat	$n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$	$n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$	$n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$
Sortare prin inserție	Matrice comandată	$n$ ${\ displaystyle n}$ $n$	$n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$	$n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$
Sortare de arbori	Căutați arborele binar	$nlog(n)$ ${\ displaystyle nlog (n)}$ ${\ displaystyle nlog (n)}$	$nlog(n)$ ${\ displaystyle nlog (n)}$ ${\ displaystyle nlog (n)}$	$nlog(n)$ ${\ displaystyle nlog (n)}$ ${\ displaystyle nlog (n)}$
Heapsort	Morman	$nlog(n)$ ${\ displaystyle nlog (n)}$ ${\ displaystyle nlog (n)}$	$nlog(n)$ ${\ displaystyle nlog (n)}$ ${\ displaystyle nlog (n)}$	$nlog(n)$ ${\ displaystyle nlog (n)}$ ${\ displaystyle nlog (n)}$

Notă

^ (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest și Clifford Stein, Capitolul 20: Fibonacci Heaps, în Introducere în algoritmi, MIT Press și McGraw-Hill, 2001, pp. 476–497, 518, ISBN 0-262-03293-7 .

Bibliografie

Camil Demetrescu, Irene Finocchi, Giuseppe Italiano, Algoritmi și structuri de date , McGraw-Hill, 2004. ISBN 88-386-6161-8 . Capitolul 8: Cozi prioritare , pp. 187-206.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest și Clifford Stein. Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest și Clifford Stein, Capitolul 20: Fibonacci Heaps, în Introducere în algoritmi, MIT Press și McGraw-Hill, 2001, pp. 476–497, 518, ISBN 0-262-03293-7 .

[1]

V · D · M Structuri de date
Tipuri	Colecție · Container
Abstract	Matrice asociativă ( Multimap ) · Listă · Stivă · Coadă ( Deque ) · prioritate coadă · Septembrie ( multiset · disjoint-set )
Matrice	Matrice de biți · Tampon circular · Matrice dinamică · Masă Hash · Matrice rar
Conectați	Lista asociațiilor · Lista Linked · Lista Omite · desfășură lista inlantuita · XOR listă înlănțuită
Copaci	B-tree · binar de căutare Arbore ( Arbore AA · Arbore AVL · arbore rosu-negru · binar de căutare copac echilibrat · copac evazat ) · Heap ( Heap binar · binom Heap · Heap Fibonacci ) · Merkle copac · copac SPQR · Arbore PQ · Binar copac indexat
Grafice	Diagrama binară de decizie · Digraf aciclic · Automat finic deterministic aciclic
Împărțirea copacilor informație spatiala	Copac Quadrament · M-tree · R-arbore ( R * arbore · R + copac ) · X-tree
Lista structurilor de date