A bináris kupac (angolul: binary heap) egy kupac adatszerkezet, mely a d-kupac egy speciális esete, ahol d=2 - azaz egy olyan kupac, ami egy bináris fa, amelyre teljesül két újabb megkötés: Teljesség: A bináris kupac egy teljes bináris fa, azaz a fa minden szintje, kivéve esetleg az utolsó szintet, fel van töltve adatokkal, és amennyiben az utolsó szint nem teljes, az balról jobbra van részben feltöltve. Kupactulajdonság: A bináris kupacban A csúcs és annak B leszármazottja között fennáll, hogy (maximum kupac esetén) kulcs(A) ≥ kulcs(B), vagy (minimum kupac esetén) kulcs(B) ≥ kulcs(A).
Műveletek A bináris kupacban a kupac alapvető műveleteit értelmezzük. A bináris kupac egyes műveleteinek leírásához C példakódot is megadtunk, amely a következő struktúrát használja: typedef struct Kupac { int *tomb; int meret; int kapacitas; } Kupac; A példákban a bináris kupacot tömb formájában implementáljuk, ezt bővebben az Implementáció szakaszban fejtjük ki. A struktúrán felül szükségünk van egy tömböt bővítő függvényre, amely a tömböt átméretezi, ha az betelik, valamint egy cserélő függvényre, amely két elemet megcserél. void bovit(Kupac *kupac) { int *tomb = malloc(2 * kupac->kapacitas * sizeof(int)); for (int i = 0; i < kupac->kapacitas; i++) { tomb[i] = kupac->tomb[i];
free(kupac->tomb); kupac->tomb = tomb; kupac->kapacitas *= 2; }
void cserel(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } A továbbiakban minden művelet leírása egy bináris max-kupacra vonatkozik. Min-kupac esetén a relációk megfordulnak. Beszúrás A kupacba való beszúráskor az elemet először a következő helyre rakjuk (azaz amennyiben a fa legalsó szintje nem teljes, akkor a szinten balról jobbra haladva a következő szabad helyre, ha pedig teljes, akkor a következő szint bal szélső elemeként szúrjuk be). Ezután megvizsgáljuk, hogy az új elem nagyobb-e, mint a közvetlen felmenője. Ha igen, megcseréljük. Ezt addig ismételjük, amíg az új felmenő nagyobb nem lesz, mint az elem, vagy az új elem a gyökérelem helyére kerül. Ezt a folyamatot up-heap-nek, azaz felfelé kupacosításnak hívjuk. A legrosszabb esetben az új elem a gyökérelem, azaz egy összehasonlításra és cserére van szükségünk minden szinten, tehát a beszúrás lépésszáma O(log n). Azonban, mivel az elemek 50%-a levélelem, és átlagosan 75%-uk a legalsó két szinten helyezkedik el, a beszúrás átlagos lépésszáma O(1). A lépésszámok nem veszik figyelembe a tömb átméretezésének költségét, azonban a tömb hatékony kezelése esetén azt mondhatjuk, hogy a beszúrás amortizált lépésszáma O(log n).
A beszúrásra kódrészlet: void felfele_kupacosit(Kupac *kupac) { int i = kupac->meret - 1; int j = (i - 1) / 2; // szülő while (i > 0 && kupac->data[i] > kupac->data[j]) { cserel(&kupac->data[i], &kupac->data[j]); i = j; j = (i - 1) / 2;
void beszur(Kupac *kupac, int ertek) { if (kupac->meret == kupac->kapacitas) { bovit(kupac); // ha a tömb betelik
kupac->tomb[kupac->meret++] = ertek; felfele_kupacosit(kupac); } Törlés Max-kupacból való törlés alatt a max-törlés műveletet értjük, azaz a maximum elem eltávolítását a kupacból. A törlés során először megcseréljük a gyökérelemet (azaz a maximum elemet) a kupac utolsó elemével (azaz a legalsó szint jobb szélső elemével), majd az így kapott levelet eltávolítjuk. A fa új gyökéreleme ekkor lehetséges, hogy nem a legnagyobb elem a fában, így a down-heap azaz lefelé kupacosítás műveletét alkalmazzuk: Ha ez az elem kisebb, mint valamely leszármazottja, megcseréljük az elemet a nagyobbik leszármazottjával, és ezt addig folytatjuk ezzel az elemmel, amíg mindkét leszármazottja kisebb nem lesz nála. Mivel mindig a nagyobbik leszármazottjával cseréltük meg, a kupactulajdonság nem sérülhetett, hiszen a helyére mindig nagyobb elem került. Így a kupac helyreáll. Legrosszabb esetben ezt az elemet a legalsó szintig le kell süllyeszteni, tehát összesen O(log n) a törlés lépésszáma.
Példakód törlésre: void lefele_kupacosit(Kupac *kupac) { int i = 0; for (;;) { int bal = 2 * i + 1, jobb = 2 * i + 2; // bal és jobb gyerek int max = (jobb < kupac->meret && kupac->tomb[jobb] > kupac->tomb[bal]) ? jobb : bal; if (bal >= kupac->meret || kupac->tomb[i] > kupac->tomb[max]) break; cserel(&kupac->tomb[i], &kupac->tomb[max]); i = max;
int maximum_torol(Kupac *kupac) { cserel(&kupac->tomb, &kupac->tomb[--kupac->meret]); lefele_kupacosit(kupac); return kupac->tomb[kupac->meret]; }
Implementáció bélyegkép|300px|jobbra|Bináris fa tömbben A bináris kupacok implementálása gyakran tömbökkel történik a más, bináris fa szerkezetű adatszerkezetek helyett. Ennek magyarázata az, hogy mivel a bináris kupac teljes bináris fa, tömbben kevesebb helyet foglal, mivel nincs szükség mutatók tárolására. A bináris kupac tömbös implementációja egy implicit adatszerkezet - azaz nincs szükségünk O(1)-nél több adat tárolására, mint maguk az adatszerkezet elemei. Tömbbel való implementációkor kétféleképpen határozhatjuk meg a gyökérelem helyét: Ha a gyökérelem a 0. indexre helyezzük, akkor felesleges helyfoglalást nem végzünk, de bonyolultabb a hozzátartozók meghatározása: egy adott i indexű elem leszármazottai 2i+1 és 2i+2, felmenője pedig (i-1)/2 alsó egészrésze. Ezt a tárolási módot alkalmaztuk a fenti példakódokban is. Ha a gyökérelem az 1. indexű, akkor a 0. indexen egyéb hasznos adatot tárolhatunk (pl. tömb mérete). A hozzátartozók meghatározása is egyszerűbb: i leszármazottai 2i és 2i+1, felmenője pedig i/2 alsó egészrésze. A bináris kupacokat implementálhatjuk a szokásos bináris faszerkezetként is, de ekkor bonyolultabb a szomszédos elemek meghatározása.
Kategória:Adatszerkezetek