Prioritate de așteptare

Clasă de coadă

Un arbore binar echilibrat vă permite să găsiți rapid orice nod. Cu toate acestea, în multe aplicații este necesar să nu primească un nod arbitrar, ci doar unul minim. O astfel de problemă apare, de exemplu, atunci când se organizează o căutare direcționată. O structură de date adecvată este o coadă de priorități.

Înainte de a discuta detaliile organizării cozii de prioritate, vom da un exemplu de (modulul queue.js) său de utilizare: În acest exemplu, coada de prioritate 50 este plasat în serie de numere aleatoare de la 0 la 99. Apoi, într-o buclă în timp ce elementele sunt ejectate din coadă, în ordinea crescătoare a valorii :

În plus față de constructor, coada clasa are 3 funcții de bază: unshift (n) - adăugarea tuturor noului element n (se deplasează elemente „din spate“ de mari dimensiuni), deplasare () - împingând elementul minim (deplasarea tuturor „înainte“) și, în cele din urmă, logic funcția empty () returnează true. dacă coada este goală (altfel, falsă).

În coada de priorități, puteți salva nu numai numere sau rânduri, ci și orice obiecte. Pentru a face acest lucru, trebuie să redefiniți funcția mai puțin:

Organizarea coadă de copaci

Ordonăm nodurile de coadă prioritare sub forma unui arbore binar. În acest arbore, cei doi copii ai fiecărui nod trebuie să fie mari sau egali cu nodul părinte. În consecință, la rădăcina copacului este cel mai mic nod. Această organizare a coadajului prioritar este numită heap binar. Mai jos este arborele coada de numere aleatoare din primul exemplu al secțiunii anterioare:

Vom păstra nodurile arborelui în array ar. Nodul rădăcină este în elementul ar [1]. Cei doi descendenți ai săi sunt în ar [2] și ar [3]. Descendenții i -lea nod (elementul ar [i]), stocate în AR [2 * i] și ar [2 * i + 1]. Datorită acestei organizări de date, arborele binar este cât mai echilibrat posibil. Dacă numărul de noduri este egal cu lungimea = 2 k -1. apoi în copac toate frunzele la nivelul inferior (k) vor fi ocupate. În general, nivelul inferior al arborelui este umplut de la stânga la dreapta și în AR [lungime] este nodul din dreapta nivel inferior. Elementul zero al array ar nu este utilizat. Mai jos este un arbore binar și reprezentarea corespunzătoare sub forma unei matrice (rețineți că elementele din matrice sunt în ordinea de copac traversal de sus în jos și de la stânga la dreapta):

Adăugarea unui element în coada de așteptare

Adăugarea este o operație destul de simplă. Nodul nou al copacului este plasat pentru prima dată în partea de jos a copacului. Pentru aceasta, introduceți noul nod din spatele ultimului nod din matrice (primul rând al funcției). Reamintim că, în cazul în care ++ stă în fața unei variabile, mai întâi este incrementat cu unu (de mai jos, aceasta crește numărul de noduri ++ this.length copac), iar apoi participă la expresia: fie ultimul element al matrice, nodul devine un nod copil cu o lungime de index / 2 === i >> 1 ("diviziune intreg"). Apoi, trebuie să fie ridicată arborele la rădăcină (rearanjare cu nodurile părinte în locuri), până când acesta este mai mic decât părintele. Pentru o operație, funcția este folosită mai puțin în mod implicit: Funcția de permutare pentru elementele i și th a array ar:

Mai jos sunt pasii secvențiali pentru a adăuga un nou nod cu o valoare de 2 și ridicarea acestuia până la locul corespunzător:

Împingerea unui element din coada de așteptare

Pentru a împinge elementul minim din coadă, trebuie să faceți următoarele: Mai întâi schimbăm rădăcina și ultimul nod al copacului. După aceasta, fosta rădăcină (nodul minimal) poate fi eliminată fără probleme, reducând numărul de lungimi ale nodurilor -. Cu toate acestea, fostul ultim nod, fiind în rădăcină, încalcă proprietățile arborelui. De aceea, trebuie să fie coborât, schimbând locurile cu descendenții săi, până când își asumă poziția "corectă" pe copac. Acest lucru se va întâmpla când ambii descendenți sunt mari sau egali cu nodul care este abandonat. Când se coboară, nodul se schimbă cu cel puțin doi descendenți, astfel încât o valoare mai mică să fie ridicată mai mare. Mai jos este un exemplu în care tasta 5 este abandonată după schimbul cu rădăcina 1:

Codul corespunzător pentru funcția de schimbare arată astfel: Utilizează funcția "curățare" a copacului, începând cu nodul nodului și de mai jos:

Utilizarea unui heap binar este cel mai simplu mod de a organiza o coadă de priorități. Pentru a susține proprietățile de heap, atunci când introduceți și ejectați un nod, este necesară o medie a operațiilor log2 N, unde N este numărul de noduri din arbore. Datorită unei anumite complicații, se poate obține complexitatea unității O (1) a adăugării (adică rata de adăugare nu depinde de numărul de noduri). În acest caz, complexitatea logaritmică a ștergerii unui nod este păstrată. Structura de date corespunzătoare este numită heapul Fibonacci.

Rețineți că coada de prioritate în același timp, este o modalitate de sortare (un anumit set de valori plasate în coada de așteptare, în cazul în care deja eliminat în ordinea dată).

Articole similare

Pagina anterioară