Desktop/Daniele/Program Editing/Progetto di informatica 2/componenti/heap.cpp

#include "heap.h"

void scambia (frequenza** v, int i, int j) 
//scambia i puntatori nell'heap
{
frequenza* app = v[i];
v[i] = v[j];
v[j] = app;
}

heap::heap(frequenza** pf, int n) //costruttore
{
v = pf;
last = n-1;
buildheap(); //invoca la buildheap perché all'inizio l'array è non è un heap
}

void heap::down(int i) 
                       //funzione down che serve nell'estrazione, mantiene 
                       //le proprietà dell'heap
{
int son = 2*i+1;
if (son == last)
   if (v[son]->freq < v[i]->freq) scambia (v,i,son);
if (son < last)
   {
   if (v[son]->freq > v[son+1]->freq) son++;
   if (v[son]->freq < v[i]->freq)
      {
      scambia (v,i,son);
      down (son);
      }
   }
}

frequenza* heap::estrai() //estrae il primo nodo (a frequenza più bassa)
{
frequenza* app = v[0];
v[0] = v[last--];
down (0);
return app;
}

int heap::lastn()
{
return last;
}
      
void heap::inserisci (frequenza* f) //inserisce il nodo con l'aiuto di up
{
v[++last] = f;
up(last);
}
       
void heap::up (int i) 
                      //fa scorrere il nodo verso l'alto conservando le
                      //proprierà dell heap
{
if (i <= 0) return;
if (v[(i-1)/2]->freq > v[i]->freq) 
   {
   scambia (v,i,(i-1)/2);
   up ((i-1)/2);
   }
}

void heap::buildheap() //costruisce lo heap a partire da un array qualsiasi
{
for (int i = last/2; i >= 0; i--)
    down (i);
}

---