// File heap.cpp
#include "heap.h"

const int DIMMAX = 100;

Heap::Heap()
{
  n = 0;
  dim = DIMMAX;
  vett = new int[dim + 1];  //salta componente 0 per semplicita'
}

Heap::Heap(int dimmax)
{
  n = 0;
  dim = dimmax;
  vett = new int[dim + 1];  //salta componente 0 per semplicita'
}

Heap::Heap(const Heap& h)
{
  n = h.n;
  dim = h.dim;
  vett = new int[dim + 1];
  for (int i = 1; i <= n; i++)
    vett[i] = h.vett[i];
}

Heap::~Heap()
{ delete [] vett; }

Heap& Heap::operator=(const Heap& h)
{
  if (this != &h) {
    delete [] vett;
    n = h.n;
    dim = h.dim;
    vett = new int[dim + 1];
    for (int i = 1; i <= n; i++)
      vett[i] = h.vett[i];
  }
  return *this;
}

// funzioni proprie dell' heap

bool Heap::EstVuoto()
{ return n == 0; }


int Heap::DammiMax()
{
  if (n == 0) return -1;

  return vett[1];
}


void Heap::Inserisci(int e)
{
  if (n >= dim) return;

  n++;
  vett[n] = e;
  FaiSalire(n);
}


void Heap::EliminaMax()
{
  if (n == 0) return;

  vett[1] = vett[n];
  n--;
  FaiScendere(1);
}


void Heap::FaiSalire(int i)
{
  if (i > 1 && vett[i] > vett[i/2]) {
    Scambia(i,i/2);
    FaiSalire(i/2);
  }
}


void Heap::FaiScendere(int i)
{
  int largest;
  int sin = 2*i;
  int des = 2*i+1;
  if (sin <= n && vett[sin] > vett[i])
    largest = sin;
  else largest = i;

  if (des <= n && vett[des] > vett[largest])
    largest = des;

  if (largest != i) {
    Scambia(i,largest);
    FaiScendere(largest);
  }
}


void Heap::Scambia(int i, int j)
{
  int temp = vett[i];
  vett[i] = vett[j];
  vett[j] = temp;
}