O grămadă binară este un arbore binar complet pentru care se execută proprietatea principală a heapului: prioritatea fiecărui vârf este mai mare decât prioritățile descendenților săi.
În cel mai simplu caz, prioritatea fiecărui vârf poate fi considerată egală cu valoarea sa. În acest caz, structura se numește max-heap. deoarece rădăcina subtreei este maximul valorilor elementelor subdirecționale.
Alternativ, dacă comparația este inversată, atunci cel mai mic element va fi întotdeauna nodul rădăcină, astfel de grămezi se numesc min-heaps.
O grămadă binară este stocată convenabil ca o matrice unidimensională și
- copilul stâng al vârfului cu index i are indexul 2 * i + 1,
- descendentul vertexului drept cu indicele i are indexul 2 * i + 2.
Rădăcina copacului (heap) este un element cu indexul 0.
Înălțimea grămezii binare este egală cu înălțimea copacului, adică,
unde N este numărul elementelor din matrice, ↑ este rotunjit până la cel mai apropiat număr întreg.
Pentru grămada prezentată
Modul de a construi un heap dintr-o matrice neordonat este de a adăuga toate elementele sale la rândul său. Estimarea timpului unui astfel de algoritm este estimată ca
Puteți construi o grămadă de pași N. Pentru a face acest lucru, trebuie să construiască mai întâi un arbore al tuturor elementelor din matrice, fără a fi nevoie să vă faceți griji cu privire la respectarea proprietățile gramada, și apoi apel metoda prin care se dispune pentru toate nodurile care au cel puțin un descendent (din cauza subarbori constând dintr-un singur nod fără descendenți, deja comandate) .
Descendenții sunt garantați că au primii vârfuri heapSize / 2, unde heapSize este mărimea heap.
Implementarea clasei Heap
static const int SIZE = 100; // mărimea maximă a heapului
int * h; // pointer la matricea heap
int HeapSize; // dimensiune heap
publice:
Heap (); // constructor de heap
void addelem (int); // adăugând un element de heap
void outHeap (); // scoateți elemente de heap sub formă de heap
void out (); // extrageți elementele de heap în formă de matrice
int getmax (); // eliminați vârful (elementul maxim)
void heapify (int); // ordonând heapul
>;
Constructor de heap
Articole similare
Trimiteți-le prietenilor: