bináris kupac
Bináris kupac egy teljes bináris fa, amelynek legfőbb kupac tulajdonság: a prioritás minden csúcsa több prioritás leszármazottja.
A legegyszerűbb esetben a prioritás minden csúcsa lehet kiindulni egyenlő értékét. Ilyen esetben, a szerkezet az úgynevezett max-kupac. mivel a gyökér részfa maximális értékeinek az elemek a részfa.
Egy másik változat szerint, ha az összehasonlítás megfordul, a legkisebb elem mindig a gyökér, mint hívás min-halom kupac.
Bináris kupac kényelmesen tárolható formában egydimenziós tömböt, és
- maradt leszármazottja csúcsú i index indexe 2 * i + 1,
- jobb leszármazottja csúcsú index i indexe 2 * i + 2.
A gyökér a fa (kupac) - az elem 0 indexű.
A magassága egy bináris kupac van a fa magasságát, vagyis
ahol N - a tömb elemeinek számát, ↑ - kerekítési a legközelebbi egész számra.
Benyújtja a kupac
Utat építeni egy halom egy rendezetlen tömb - az, hogy adjunk minden elemét viszont. Az idő becslése az algoritmus a becslések szerint
Lehetséges, hogy egy csomó N lépésben. Ehhez először meg kell építeni egy fa az összes elem a tömbben, anélkül, hogy aggódnia megfelelő tulajdonságait a halom, majd hívja a rendelési eljárás összes csúcsot, amely legalább egy leszármazottja (mert részfák amely egyetlen csúcs nélkül leszármazottai, már megrendelt) .
Leszármazottai garantált, hogy az első heapSize / 2 csúcsú ahol heapSize - kupacmérete.
Végrehajtása a kupac osztály
statikus const int SIZE = 100; // maximális kupacmérete
int * h; // mutató egy tömb kupac
int HeapSize; // mérete kupac
nyilvános:
Heap (); // konstruktor kupac
void addelem (int); // hozzá a halom elem
érvényteleníti outHeap (); // nyomtatni a halom elemek formájában halom
érvényteleníti ki (); // nyomtatni a halom elemek formájában egy tömb
int getmax (); // távolítsa el a tetejét (a maximális elem)
érvényteleníti heapify (int); // rendelési kupac
>;