Coadă de găleată - Bucket queue

Coadă de găleată
Coadă de găleată
	O serie de găleți, potrivite pentru priorități cuprinse între 1 și 6. Elementul cu prioritate minimă poate fi găsit în cupa cea mai stângă, ne-goală.
Tip	coadă prioritară
Inventat	1969
Inventat de	Robert Dial
Complexitatea timpului în notația O. mare

O coadă de bucket este o structură de date care implementează tipul de date de coadă prioritară : menține o colecție dinamică de elemente cu priorități numerice și permite accesul rapid la elementul cu prioritate minimă (sau maximă). În coada de bucket, prioritățile trebuie să fie întregi și sunt potrivite în special aplicațiilor în care prioritățile au o gamă mică. O coadă de bucket are forma unei matrice de găleți : o structură de date matrice , indexată în funcție de priorități, ale cărei celule conțin colecții de articole cu aceeași prioritate una ca cealaltă. Cu această structură de date, inserarea elementelor și modificarea priorității lor necesită timp constant . Căutarea și eliminarea elementului cu prioritate minimă necesită timp proporțional cu numărul de găleți sau, prin menținerea unui indicator către cea mai recentă găleata găsită, în timp proporțional cu diferența de priorități între operațiile succesive.

Coada de găleată este analogul cu coadă de prioritate pentru sortarea porumbelelor (numită și sortare de găleată), un algoritm de sortare care plasează elemente în găleți indexate după prioritățile lor și apoi concatenează gălețile. Utilizarea unei cozi de găleată ca coadă de prioritate într-un sortare de selecție oferă o formă a algoritmului de sortare a porumbeilor. Cozile pentru cupe se mai numesc cozi cu prioritate pentru cupe sau cozi cu prioritate la înălțime limitată . Atunci când sunt utilizate pentru aproximări cuantificate la prioritățile numărului real , acestea sunt numite și cozi de prioritate neordonate sau cozi de pseudo prioritate . Acestea sunt strâns legate de coada calendaristică , o structură care utilizează o matrice similară de găleți pentru stabilirea priorităților exacte prin numere reale.

Aplicațiile cozii de bucket includ calculul degenerescenței unui grafic , algoritmi rapidi pentru căile mai scurte și căi largi pentru graficele cu greutăți care sunt întregi mici sau sunt deja sortate și algoritmi de aproximare lacomi pentru problema acoperirii setate . Versiunea cuantificată a structurii a fost, de asemenea, aplicată planificării și cuburilor de marș în grafică pe computer . Prima utilizare a cozii de bucket a fost într-un algoritm de cale mai scurt de Dial (1969) .

Operațiune

Structura de bază a datelor

O coadă de bucket poate gestiona elemente cu priorități întregi în intervalul de la 0 sau 1 până la un $C$ legat cunoscut și operații care introduc elemente, modifică prioritatea elementelor sau extrag (găsește și elimină) elementul care are minimul (sau maximă) prioritate. Acesta constă dintr-o matrice $A$ de structuri de date pentru containere ; în majoritatea surselor, aceste containere sunt liste dublu legate, dar pot fi alternativ matrici dinamice sau seturi dinamice . Containerui în $p$ th celula array $A [p]$ stochează colectarea elementelor a căror prioritate este $p$ .

O coadă de găleată poate gestiona următoarele operații:

Pentru a insera un element $x$ cu prioritate $p$ , adăugați $x$ în containerul de la $A [p]$ .
Pentru a schimba prioritatea unui element, scoateți-l din container pentru vechea sa prioritate și reintroduceți-l în container pentru noua sa prioritate.
Pentru a extrage un element cu prioritatea minimă sau maximă, efectuați o căutare secvențială în matrice pentru a găsi primul sau ultimul container, respectiv gol, alegeți un element arbitrar din acest container și scoateți-l din container.

În acest fel, inserțiile și modificările de prioritate necesită timp constant, iar extragerea elementului de prioritate minimă sau maximă necesită timp $O (C)$ .

Optimizări

Ca o optimizare, structura de date poate începe fiecare căutare secvențială a unei bucle ne-goale la cea mai recent găsite găleți ne-goale în loc de la începutul matricei. Acest lucru se poate face în două moduri diferite, leneș (întârzierea acestor căutări secvențiale până când sunt necesare) sau dornic (efectuarea căutărilor înainte de timp). Alegerea momentului de efectuare a căutării afectează care dintre operațiunile structurii de date este încetinită de aceste căutări. Versiunea originală a structurii Dial a folosit o căutare leneșă. Acest lucru se poate face prin menținerea unui index $L$ care este o limită inferioară a priorității minime a oricărui element aflat în prezent în coadă. Când introduceți un element nou, $L$ trebuie actualizat la minimul vechii sale valori și prioritatea noului element. Când căutați elementul cu prioritate minimă, căutarea poate începe de la $L$ în loc de la zero, iar după căutare, $L$ trebuie lăsat egal cu prioritatea găsită în căutare. Alternativ, versiunea dornică a acestei optimizări păstrează $L$ actualizat, astfel încât să indice întotdeauna către primul compartiment ne-gol. Când introduceți un element nou cu o prioritate mai mică decât $L$ , structura de date setează $L$ la noua prioritate și, atunci când eliminați ultimul element dintr-o bucket cu prioritatea $L$ , efectuează o căutare secvențială prin indexuri mai mari până la găsirea unei bucket ne-goale și setarea $L$ la prioritatea cupei rezultate.

In oricare dintre aceste două variante, fiecare căutare secvențială necesită timp proporțional cu diferența dintre valorile vechi și noi de $L$ . Acest lucru ar putea fi semnificativ mai rapid decât timpul $O (C)$ legat de căutările din versiunea neoptimizată a structurii de date. În multe aplicații ale cozilor de prioritate, cum ar fi algoritmul lui Dijkstra , prioritățile minime formează o secvență monotonă , permițând utilizarea unei cozi de prioritate monotone . În aceste aplicații, atât pentru variațiile leneșe, cât și dornice ale structurii optimizate, căutările secvențiale pentru găleți care nu sunt goale acoperă domenii disjuncte de găleți. Pentru că fiecare compartiment este în cel mult unul dintre aceste intervale, numerele lor de pași adăugați la cel mult $C$ . Prin urmare, în aceste aplicații, timpul total pentru o secvență de $n$ operații este $O (n + C)$ , mai degrabă decât legătura de timp $O (nC)$ mai lentă care ar rezulta fără această optimizare. O optimizare corespunzătoare poate fi aplicată în aplicații în care se utilizează o coadă de bucket pentru a găsi elemente cu prioritate maximă, dar în acest caz ar trebui să mențină un index care să limiteze superior prioritatea maximă, iar căutarea secvențială pentru o bucket ne-goală ar trebui să continue în jos de la această limită superioară.

O altă optimizare (dat deja de Dial 1969 ) poate fi utilizată pentru a economisi spațiu , atunci când prioritățile sunt monotone și, pe tot parcursul unui algoritm, întotdeauna se încadrează într - un interval de $r$ valori , mai degrabă decât se extinde pe toată gama de la 0 la $C$ . În acest caz, se poate indexa matricea după prioritățile modulului $r$ mai degrabă decât după valorile lor reale. Căutarea elementului de prioritate minimă ar trebui să înceapă întotdeauna de la minimul anterior, pentru a evita prioritățile mai mari decât cele minime, dar care au moduli mai mici. În special, această idee poate fi aplicată în algoritmul lui Dijkstra pe grafice ale căror lungimi de margine sunt întregi în intervalul de la 1 la $r$ .

Deoarece crearea unei noi cozi de compartimentare implică inițializarea unei matrice de găleți goale, acest pas de inițializare necesită timp proporțional cu numărul de priorități. O variație a cozii de găleată descrisă de Donald B. Johnson în 1981 stochează în schimb doar gălețile care nu sunt goale într-o listă legată, sortate după prioritățile lor și folosește un arbore de căutare auxiliar pentru a găsi rapid poziția din această listă legată pentru orice nou găleți. Este nevoie de timp $O (log log C)$ pentru a inițializa această variantă de structură, timp constant pentru a găsi un element cu prioritate minimă sau maximă și timp $O (log log D)$ pentru a insera sau șterge un element, unde $D$ este diferența dintre cel mai apropiat priorități din ce în ce mai mari față de prioritatea elementului inserat sau șters.

Exemplu

De exemplu, luați în considerare o coadă de bucket cu patru priorități, numerele 0, 1, 2 și 3. Se compune dintr-un tablou ale cărui patru celule conțin fiecare o colecție de elemente, inițial goale. În sensul acestui exemplu, poate fi scrisă ca o secvență parantezele de patru seturi: . Luați în considerare o secvență de operații în care inserăm două elemente și cu aceeași prioritate 1, inserăm un al treilea element cu prioritatea 3, schimbăm prioritatea de la 3 și apoi efectuați două extracții ale elementului cu prioritate minimă. ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle A = [\ emptyset, \ emptyset, \ emptyset, \ emptyset]}$ ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle z}$ ${\ displaystyle x}$

După inserarea cu prioritatea 1 ,. ${\ displaystyle x}$ ${\ displaystyle A = [\ emptyset, \ {x \}, \ emptyset, \ emptyset]}$
După inserarea cu prioritatea 1 ,. ${\ displaystyle y}$ ${\ displaystyle A = [\ emptyset, \ {x, y \}, \ emptyset, \ emptyset]}$
După introducerea z cu prioritatea 3 ,. ${\ displaystyle A = [\ emptyset, \ {x, y \}, \ emptyset, \ {z \}]}$
Schimbarea priorității lui x de la 1 la trei implică eliminarea acestuia și adăugarea acestuia la , după care . ${\ displaystyle A [1]}$ ${\ displaystyle A [3]}$ ${\ displaystyle A = [\ emptyset, \ {y \}, \ emptyset, \ {x, z \}]}$
Extragerea elementului cu prioritate minimă, în versiunea de bază a cozii de bucket, caută de la începutul anului pentru a găsi primul său element ne-gol: este gol , dar , un set ne-gol. Alege un element arbitrar al acestui set (singurul element ) ca element cu prioritate minimă. Îndepărtarea din structură a frunzelor . ${\ displaystyle A}$ ${\ displaystyle A [0]}$ ${\ displaystyle A [1] = \ {y \}}$ ${\ displaystyle y}$ ${\ displaystyle y}$ ${\ displaystyle A = [\ emptyset, \ emptyset, \ emptyset, \ {x, z \}]}$
A doua operațiune de extract, în versiunea de bază a cozii de cupă, căutări din nou de la începutul matrice: , , , care nu este gol. În variantele îmbunătățite ale cozii de găleată, această căutare începe în loc de la ultima poziție care sa dovedit a fi necompletată . În ambele cazuri, se găsește primul set ne-gol. Unul dintre elementele sale este ales în mod arbitrar ca element cu prioritate minimă; de exemplu, ar putea fi aleasă. Acest element este eliminat, lăsând . ${\ displaystyle A [0] = \ emptyset}$ ${\ displaystyle A [1] = \ emptyset}$ ${\ displaystyle A [2] = \ emptyset}$ ${\ displaystyle A [3] = {}}$ ${\ displaystyle A [1]}$ ${\ displaystyle A [3] = \ {x, z \}}$ ${\ displaystyle z}$ ${\ displaystyle A = [\ emptyset, \ emptyset, \ emptyset, \ {x \}]}$

Aplicații

Degenerarea grafică

O coadă de găleată poate fi utilizată pentru a menține vârfurile unui grafic nedirecționat , prioritizate de gradele lor și pentru a găsi și elimina în mod repetat vârful de grad minim. Acest algoritm lacom poate fi folosit pentru a calcula degenerarea unui grafic dat, egal cu cel mai mare grad al oricărui vârf în momentul eliminării acestuia. Algoritmul ia timp liniar , cu sau fără optimizarea care menține o limită inferioară asupra priorității minime, deoarece fiecare vârf se găsește în timp proporțional cu gradul său și suma tuturor gradelor de vârf este liniară în numărul de muchii ale graficului.

Algoritmul Dial pentru cele mai scurte căi

În algoritmul lui Dijkstra pentru cele mai scurte căi în grafice direcționate cu greutăți de margine care sunt numere întregi pozitive, prioritățile sunt monotone, iar o coadă de găleată monotonă poate fi utilizată pentru a obține un timp legat de $O (m + dc)$ , unde $m$ este numărul de margini , $d$ este diametrul rețelei și $c$ este costul maxim (întreg) al legăturii. Această variantă a algoritmului lui Dijkstra este cunoscută și sub numele de algoritmul lui Dial , după Robert B. Dial, care l-a publicat în 1969. Aceeași idee funcționează, folosind o coadă de cupă cuantizată, pentru grafice cu greutăți pozitive ale muchiei reale atunci când raportul dintre maxim și greutatea minimă este cel mult $c$ . În această versiune cuantizată a algoritmului, vârfurile sunt procesate în ordine, comparativ cu rezultatul cu o coadă de prioritate necuantizată, dar se găsesc încă cele mai scurte căi corecte. În acești algoritmi, prioritățile vor acoperi doar o gamă de lățime $c + 1$ , astfel încât optimizarea modulară poate fi utilizată pentru a reduce spațiul la $O (n + c)$ .

O variantă a aceluiași algoritm poate fi utilizată pentru cea mai largă problemă de cale . În combinație cu metode pentru partiționarea rapidă a greutăților marginilor care nu sunt întregi în subseturi cărora li se pot atribui priorități întregi, aceasta conduce la soluții în timp aproape liniar pentru versiunea cu o singură sursă a destinației unice a celei mai largi probleme de cale.

Coperta setului lacom

Problema acoperirii setului are ca intrare o familie de seturi . Rezultatul ar trebui să fie o subfamilie a acestor seturi, cu aceeași uniune ca familia originală, incluzând cât mai puține seturi. Este NP-hard , dar are un algoritm de aproximare lacom care atinge un raport de aproximare logaritmică, în esență cel mai bun posibil, cu excepția cazului în care P = NP . Acest algoritm de aproximare își selectează subfamilia alegând în mod repetat un set care acoperă numărul maxim posibil de elemente neacoperite rămase. Un exercițiu standard în proiectarea algoritmului solicită o implementare a acestui algoritm care necesită timp liniar în dimensiunea de intrare, care este suma dimensiunilor tuturor seturilor de intrare.

Acest lucru poate fi rezolvat folosind o coadă de seturi de seturi din familia de intrare, prioritizată de numărul de elemente rămase pe care le acoperă. De fiecare dată când algoritmul lacom alege un set ca parte a rezultatului său, elementele setului nou acoperite trebuie scăzute din prioritățile celorlalte seturi care le acoperă; pe parcursul algoritmului, numărul acestor modificări de priorități este doar suma dimensiunilor seturilor de intrare. Prioritățile sunt numere întregi în scădere monotonă, delimitate de numărul de elemente care trebuie acoperite. Fiecare alegere a algoritmului lacom implică găsirea setului cu prioritatea maximă, care se poate face prin scanarea în jos prin gălețile cozii de găleată, începând de la cea mai recentă valoare maximă anterioară. Timpul total este liniar în dimensiunea de intrare.

Programare

Cozile de bucket pot fi utilizate pentru a programa sarcini cu termene limită, de exemplu în redirecționarea pachetelor pentru date de internet cu garanții de calitate a serviciului . Pentru această aplicație, termenele limită ar trebui să fie cuantificate în intervale discrete, iar sarcinile ale căror termene limită se încadrează în același interval sunt considerate a avea o prioritate echivalentă.

O variație a structurii de date a cozii de bucket cuantificate, coada calendaristică , a fost aplicată pentru planificarea simulărilor de evenimente discrete , în care elementele din coadă sunt evenimente viitoare prioritizate de timpul din cadrul simulării în care evenimentele ar trebui să se întâmple. În această aplicație, ordonarea evenimentelor este critică, astfel încât prioritățile nu pot fi aproximate. Prin urmare, coada de calendar efectuează căutări pentru elementul cu prioritate minimă într-un mod diferit de o coadă de găleată: în coada de găleată, orice element din prima găleată ne-goală poate fi returnat, dar în schimb coada de calendar caută toate elementele din acea găleată pentru a determina care dintre ele are cea mai mică prioritate necuantizată. Pentru a menține aceste căutări rapide, această variație încearcă să păstreze numărul de găleți proporțional cu numărul de elemente, prin ajustarea scalei de cuantificare și reconstruirea structurii datelor atunci când aceasta se dezechilibrează. Cozile de calendar pot fi mai lente decât cozile de găleți în cel mai rău caz (când multe elemente aterizează în aceeași cea mai mică cupă), dar sunt rapide când elementele sunt distribuite uniform între găleți, determinând dimensiunea medie a găleții să fie constantă.

Marș rapid

În matematica aplicată și metodele numerice pentru rezolvarea ecuațiilor diferențiale , au fost folosite cozi de prioritate neordonate pentru a prioritiza pașii metodei de marșare rapidă pentru rezolvarea problemelor de valoare la graniță ale ecuației Eikonal , utilizate pentru modelarea propagării undelor . Această metodă găsește momentele în care o graniță în mișcare traversează un set de puncte discrete (cum ar fi punctele unei grile întregi) folosind o metodă de prioritizare asemănătoare unei versiuni continue a algoritmului Dijkstra , iar timpul său de rulare este dominat de coada sa prioritară. dintre aceste puncte. Poate fi accelerat până la timp liniar prin rotunjirea priorităților utilizate în acest algoritm la numere întregi și folosind o coadă de bucket pentru aceste numere întregi. La fel ca în algoritmii lui Dijkstra și Dial, prioritățile sunt monotone, deci marșarea rapidă poate utiliza optimizarea monotonă a cozii de bucket și analiza acesteia. Cu toate acestea, discretizarea introduce unele erori în calculele rezultate.

Vezi si

Soft heap , un mod diferit de a accelera cozile de priorități prin utilizarea unor priorități aproximative

Languages

In other projects