arbore binar
Printre copaci emit o subclasă specială numită arbori binari. arbore binar - arbore înrădăcinate, astfel încât fiecare nod are cel mult două filiale, de multe ori în mod clar ordonate: stânga și dreapta. De exemplu, este un arbore binar:
Printre arbori binari aloca separat arbore binar complet. toate ale căror vârfuri au două filiale, cu excepția frunzele, care sunt situate la aceeași adâncime:
De asemenea, este adesea menționată arbori binari compleți, care au umplut complet toate nivelurile, cu excepția ultima:
Când 1 vârfuri de indexare prin nivelurile indicate mai sus, există formule simple pentru tranziția între noduri. Pentru un vârf cu indice de $ v $ formulă de coborâre spre stânga, coborând spre dreapta, și va ridica după cum urmează:
$$ l = 2v \\ r = 2v + 1 \\ p = \ stângă \ lfloor \ dreapta \ rfloor $$
În acest sens, copacii binare complete de multe ori stocate nu în forma listei de adiacenta, sub forma unei matrice simplu, în cazul în care $ copac [v] $ - o valoare atribuită la partea de sus a indicelui $ v $. Pentru parcurgeri folosind formule de mai sus.
Trebuie remarcat faptul că înălțimea (numărul de niveluri) arbore binar complet de $ N $ vârfuri este egal cu $ \ log n $. Această proprietate este adesea folosit pentru a evalua complexitatea diferitelor algoritmi.
Un buchet (morman limba engleză.) - una dintre cele mai simple structuri de date bazate pe copaci. O grămadă de utilizat pentru a menține un set de elemente cu capacitatea de a gasi rapid maxim (sau minim, nu contează).
mănunchi clasică acceptă următoarele operații:
- Adăugați element (dificultate: $ O (\ log N) $)
- Găsiți maxim (dificultate: $ O (1) $)
- Se extrage elementul maxim (dificultate: $ O (\ log N) $)
într-o grămadă de articole sunt stocate sub forma unui arbore binar complet. proprietatea sa principală (invariantul heap) este formulat după cum urmează:
Elementul de la fiecare nod este mai mare sau elemente egale în toate nodurile copil.
Din această proprietate rezultă că elementul minim va fi întotdeauna la rădăcina copacului.
Când adăugați o grămadă de nouă intrare este atribuit primul indice disponibile. Aceasta este, arborele binar este umplut prin nivelurile de la stânga la dreapta. După adăugarea elementului este posibil ca încetarea invariante heap să fie realizată, ca un element nou va fi mai mare decât strămoșul său direct. În astfel de cazuri, pur și simplu schimb elementul cu strămoș direct. Dacă invarianta heap nu este încă mulțumit, vom schimba locul cu un nou strămoș, și așa mai departe până când grămada nu este normal. Această operație se numește împingere în sus.
Atunci când extragerea elementului de maxim folosim următorul truc: mutați ultimul element al heap (dreapta- on ultimul nivel) în rădăcina copacului, în loc de vârf la distanță. Acest lucru este aproape sigur încalcă un invariant, ca noul „maxim“, va fi mai puțin elemente în nodurile copil. Să comparăm cele două elemente copil, pentru a alege una, și a schimbat locurile cu curent „maxim“ lui. Se repetă acest proces până când invariantul nu este restabilită. Aceasta se numește un push-down.
punerea în aplicare
Conceptul de coadă cu prioritate
Puteți auzi în loc de termenul „buchet“, termenul de „coada de prioritate“. În practică, ele sunt folosite alternativ, deși diferența în valoarea încă prezentă.
Coada cu prioritate - pe o structură abstractă de date, care permite menținerea unui set de elemente, localiza și a prelua cel puțin de la ea, la, în timp ce o grămadă de - structuri de date specifice bazate pe un arbore binar complet. Orice buchet este o coadă de prioritate, dar nu orice coada de așteptare cu prioritate (în teorie) este un morman (în practică, aproape orice). Puteți implementa suport pentru extragerea multiple cu maxim o matrice simplu, acesta va fi operațional complexitatea $ O (N) $, dar să fie încă o coadă de prioritate.
(Dacă sunteți familiarizat cu programarea orientată pe obiecte, coada cu prioritate - interfață și o grămadă. - o clasă pe care îl pune în aplicare)
Coada cu prioritate în biblioteca standard C ++
In standard C ++ bibliotecă heap implementare prezent care suportă toate operațiile de mai sus. Această clasă de std :: priority_queue
Implicit este o grămadă de a găsi maxim. Pentru a utiliza heap pentru a găsi minimul pe care trebuie să utilizați tipul std :: priority_queue