Coada prioritară (programare)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 25 martie 2021; verificările necesită 2 modificări .

O  coadă de prioritate este un tip abstract de date în programare care acceptă două operații obligatorii - adăugați un element și extrageți maximul [1] (minimum). Se presupune că pentru fiecare element este posibil să se calculeze prioritatea acestuia  - un număr real sau, în cazul general, un element al unei mulțimi ordonate liniar [2] .

Descriere

Principalele metode implementate de coada de prioritate sunt următoarele [2] [3] [1] :

În acest caz, o valoare a cheii mai mică corespunde unei priorități mai mari.

În unele cazuri, este mai natural ca cheia să crească împreună cu prioritatea. Atunci a doua metodă poate fi numită extract_maximum()[1] .

Există o serie de implementări în care ambele operații de bază sunt efectuate în cel mai rău caz în timp limitat (vezi „O” mare și „o” mic ), unde  este numărul de perechi stocate.

Exemple

Ca exemplu de coadă de prioritate, luați în considerare lista de sarcini a unui lucrător. Când termină o sarcină, trece la următoarea - cea mai mare prioritate (cheia va fi reciproca priorității) - adică efectuează operația de extragere a maximului. Șeful adaugă sarcini la listă, indicând prioritatea acestora, adică efectuează operația de adăugare a unui element.

Extensii de coadă prioritare

În practică, interfața de coadă prioritară este adesea extinsă cu alte operațiuni [4] [3] :

În cozile de prioritate indexate (adresate [5] ), este posibilă accesarea elementelor prin index. Astfel de cozi pot fi folosite, de exemplu, pentru a îmbina mai multe secvențe sortate (multiway merge) [1] .

Poate fi luată în considerare și coada cu prioritate dublă (DEPQ ) ,  în care există operații de acces atât la elementul minim, cât și la cel maxim [6] .

Implementări

Coada de prioritate poate fi implementată pe baza diferitelor structuri de date.

Cele mai simple (și nu foarte eficiente) implementări pot folosi o matrice neordonată sau ordonată , o listă legată , potrivită pentru cozi mici. În acest caz, calculele pot fi fie „leneșe” (severitatea calculelor se transferă la extragerea elementului) și timpurii (dornici), când introducerea elementului este mai dificilă decât extragerea acestuia. Adică, una dintre operații poate fi efectuată în timp , iar cealaltă - în cel mai rău caz pentru , unde  este lungimea cozii [1] .

Mai eficiente sunt implementările bazate pe heap , unde ambele operații pot fi efectuate în cel mai rău caz în timp [1] . Acestea includ grămada binar , grămada binomială , grămada Fibonacci , grămada de împerechere[6] .

Tipul de date abstracte (ATD) pentru coada de prioritate este derivat din heap ADT prin redenumirea funcțiilor corespunzătoare. Valoarea minimă (maximă) este întotdeauna în partea de sus a heap-ului [7] .

Exemplu Python

Biblioteca standard Python conține un modul heapq[8] care implementează o coadă de prioritate [9] :

# import două funcții de coadă cu numele folosite în acest articol din heapq import heappush ca insert , heappop ca extract_maximum pq = [] # inițializați inserarea listei ( pq , ( 4 , 0 , "p" )) # inserați elementul "p" în coadă " cu index 0 și prioritate 4 inserați ( pq , ( 2 , 1 , " e " ) ) inserați ( pq , ( 3 , 2 , " a " ) ) inserați ( pq , ( 1 , 3 , " h ") )) # decrescătoareordineînelementepatruceleimprimați _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Acest exemplu va scoate cuvântul „heap”.

Note

  1. ↑ 1 2 3 4 5 6 Sedgewick, Wayne, 2011 .
  2. ↑ 1 2 Aho, Hopcroft, Ullman, 2000 .
  3. ↑ 1 2 Kormen și colab., 2005 .
  4. ↑ Robert Sedgewick. Algoritmi în C++, părțile 1–4: noțiuni fundamentale, structura datelor, sortare, căutare. - A treia editie. — Addison-Wesley Professional. — 752 p. - ISBN 978-0-7686-8533-6 .
  5. ↑ Mehlhorn, Sanders, 2008 .
  6. ↑ 1 2 Sahni, Mehta, 2018 .
  7. ↑ Rabhi, Lapalme, 1999 .
  8. ↑ 8.4. heapq - Algoritm de coadă heap . Consultat la 25 noiembrie 2014. Arhivat din original la 4 decembrie 2017.
  9. ↑ David Beazley, Brian K. Jones. 1.5. Implementarea unei cozi de prioritate // Cartea de bucate Python. - editia a 3-a. - O'Reilly Media, Inc., 2013. - 706 p. — ISBN 978-1-4493-4037-7 .

Literatură

  • Kormen, T., Leizerson, C., Rivest, R., Stein, K. Algoritmi: construcție și analiză = Introduction to Algorithms / Ed. I. V. Krasikova. - Ed. a II-a - M . : Williams , 2005. - 1296 p. — ISBN 5-8459-0857-4 .
  • Aho A. W., Hopcroft J. E., Ullman J. D. Structuri și algoritmi de date. - Williams, 2000. - 384 p. — ISBN 9785845901224 . , 4.10. Cozi prioritare
  • Robert Sedgewick; Kevin Wayne. 2.4 Cozi prioritare // Algoritmi. - A patra editie. - Addison-Wesley Professional, 2011. - 992 p. — ISBN 978-0-13-276257-1 .
  • Gerth Stølting Brodal, Chris Okasaki. Cozi prioritare optime pur funcționale  // Seria de rapoarte BRICS. - Departamentul de Informatică Universitatea din Aarhus, 1996. - Nr. RS-96-37 . — ISSN 0909-0878 .
  • Fethi Rabhi și Lapalme, G. Algoritmi: O abordare de programare funcțională . - Addison-Wesley, 1999. - P.  92-93 , 106-107. — 235p. — ISBN 9780201596045 .
  • Sartaj Sahni și Dinesh P. Mehta. Partea a II-a: Cozi prioritare // Manual de structuri și aplicații de date. — Ed. a II-a. - Chapman și Hall / CRC, 2018. - 1100 p. — ISBN 9781498701853 .
  • Mehlhorn, Kurt, Sanders, Peter. 6. Cozi prioritare // Algoritmi și structuri de date: Setul de instrumente de bază. - Springer, 2008. - 300 p. — ISBN 978-3-540-77978-0 .

Link -uri

  • Cozile prioritare pentru Ruby :
  • Implementarea cozii de prioritate Haskell verificată de Coq :