Cozi cu prioritate (coada de priorități engleză) - un tip abstract de date în programare. sprijinirea a două operațiuni obligatorii - adăugați un element și extrageți maximul (minim). Se presupune că pentru fiecare element este posibil să se calculeze prioritatea sa - un număr real sau, în general, un element al unui set ordonat liniar.
Metodele de bază implementate de coada de priorități sunt:
- inserați (cheie, valoare) - adaugă un cuplu (cheie, valoare) în depozit;
- extract_minimum () - returnează o pereche (cheie, valoare) cu valoarea minimă a cheii, scoate-o din depozit.
În acest caz, o valoare cheie mai mică corespunde unei priorități mai mari.
În unele cazuri, creșterea cheii este mai naturală, împreună cu prioritatea. Apoi, a doua metodă poate fi numită extract_maximum ().
Există o serie de implementări în care ambele operații de bază sunt efectuate în cel mai rău caz într-un timp limitat de O (log n) - numărul de perechi stocate.
Ca exemplu de coadă de priorități, puteți vizualiza lista de sarcini a angajatului. Când termină o singură sarcină, el merge la următoarea - cea mai mare prioritate (cheia va fi valoarea, prioritatea inversă) - adică efectuează operația de extragere a maximului. Managerul adaugă sarcini în listă, indicând prioritatea lor, adică efectuând operația de adăugare a unui element.
Imbunatatiri frontale cu editarea prioritatilor
În practică, interfața cozii cu prioritate este adesea extinsă de alte operații:
- returnați elementul minim fără a îl elimina din coadă
- schimba prioritatea unui element arbitrar
- elimina un element arbitrar
- îmbinarea a două cozi într-una
O coadă cu priorități poate fi implementată pe baza diferitelor structuri de date.
Cele mai simple implementări (și nu foarte eficiente) pot utiliza o matrice neordonată sau ordonată. listă conectată. potrivite pentru explozii mici. În acest caz, calculele pot fi fie "leneși" (gravitatea calculelor este transferată la extragerea elementului), fie cele timpurii (dornici), atunci când introducerea unui element este mai dificil decât extragerea acestuia. Aceasta este, o operație poate fi efectuată în timp O (1)
Mai eficiente sunt implementările bazate pe heap. unde ambele operații pot fi efectuate în cel mai rău caz într-un timp O (log N)
Tipul de date abstract (ATD) pentru coada de priorități este obținut din ADT-ul de heap redenumind funcțiile corespunzătoare. Valoarea minimă (maximă) este întotdeauna în partea superioară a heapului.
Exemplu Python
Biblioteca standard Python conține modulul heapq. Implementarea unei coada de priorități:
Acest exemplu va afișa cuvântul "heap".
Articole similare
Trimiteți-le prietenilor: