Bináris kupac

Bináris kupac
Típus	Fa
Komplexitás (O jelöléssel)
Tárigény	O(n)
Beszúrás	Θ(log n)
Törlés	Θ(log n)

A bináris kupac 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 heap
{
  int* elemek;
  int max;
  int darab;
} heap;

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.

void bovit(heap* h)
{
  int* temp = (int*)malloc(2*h->max*sizeof(int));
  int i;
  for (i = 0; i < max; i++)
  {
    temp[i] = elemek[i];
  }
  h->max *= 2;
  h->elemek = temp;
}

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 beszur(heap* h, int n)
{
  int index = h->darab;
  if (h->max == h->darab)
  {
    bovit(h); // ha a tömb betelik
  }
  h->elemek[index] = n; // beszúrás az utolsó helyre
  h->darab++;
  while (index && h->elemek[index] > h->elemek[(index - 1) / 2]) // felfelé kupacosítás ciklus
  {
    int temp;
    temp = h->elemek[index];
    h->elemek[index] = h->elemek[(index - 1) / 2];
    h->elemek[(index - 1) / 2] = temp;
    index = (index - 1) / 2;
  }
}

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:

int maxtor(heap* h, int n)
{
  int temp, index = 0, kupac = 0, ret;
  if (!h->darab)
  {
    return -1;
  }
  ret = temp = h->elemek[0];
  h->elemek[0] = h->elemek[h->darab - 1];
  h->elemek[h->darab - 1] = temp;
  h->darab--;
  while (!kupac)
  {
    int maxindex = -1;
    if (index * 2 + 1 < darab && h->elemek[index * 2 + 1] > h->elemek[index])
    {
      maxindex = index * 2 + 1;
    }
    if (index * 2 + 2 < darab && h->elemek[index * 2 + 2] > h->elemek[index])
    {
      if ((maxindex > -1 && h->elemek[index * 2 + 2] > h->elemek[maxindex]) || maxindex == -1)
      {
        maxindex = index * 2 + 2;
      }
    if (maxindex == -1)
      kupac = 1;
    else
    {
      temp = h->elemek[maxindex];
      h->elemek[maxindex] = h->elemek[index];
      h->elemek[index] = temp;
      index = maxindex;
    }
  }
  return ret;
}

Implementáció

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.