Version:0.9
StartHTML:0000000105
EndHTML:0000008105
StartFragment:0000000152
EndFragment:0000008071
/******************************************************/
/*************** Isidro Pastor Jorda ******************/
/******************************************************/
/****************** Telematica ************************/
/******************** FPII ****************************/
/****************** Practica 8 ************************/
/******************************************************/
#include "00maxHeap.h"
/*****************************************************************************
* Funcion: Heap
* Descripcion: Constructor de clase Heap
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Inicializa un objeto de la clase Heap
*****************************************************************************/
Heap::Heap()
{
num = -1;
};
/*****************************************************************************
* Funcion: Insertar
* Descripcion: Inserta un elemento en el objeto Heap que hace la llamada
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* x E Valor que queremos insertar
*
*
*
* Valor devuelto:
* Devuelve true si el vector esta lleno y no podemos insertar, false en caso contrario
*****************************************************************************/
bool Heap::Insertar(Valor x)
{
bool error;
if (num == MAX-1)
error = true;
else
{
error = false;
num++;
info[num] = x;
Subir(num);
}
return(error);
};
/*****************************************************************************
* Funcion: EliminarMaximo
* Descripcion: Elimina el maximo del objeto Heap de maximos que hace la llamada
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Devolvera true si se ha podido elimiar el maximo, true en caso contrario
*****************************************************************************/
bool Heap::EliminarMaximo()
{
bool ok;
Valor aux;
if (num < 0)
ok = false;
else
{
ok = true;
info[0] = info[num];
num--;
Bajar(0);
} // else
return(ok);
};
/*****************************************************************************
* Funcion: ConsultarMaximo
* Descripcion: Consulta el valor maximo en un Heap de maximos
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* res E/S Variable por referencia donde almacenaremos la consulta
*
*
*
* Valor devuelto:
* Devuelve true si la consulta se ha realizado con exito, false en caso contrario
*****************************************************************************/
bool Heap::ConsultarMaximo (Valor & res)
{
bool ok;
if (num < 0)
ok = false;
else
{
ok = true;
res = info[0];
}
return(ok);
};
/*****************************************************************************
* Funcion: HeapVacio
* Descripcion: Indica si el objeto Heap que hace la llamada es vacio
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
*
*
*
*
* Valor devuelto:
* Devolvera true si el objeto heap esta vacio, true en caso contrario
*****************************************************************************/
bool Heap::HeapVacio()
{
return(num == -1);
};
/*****************************************************************************
* Funcion: Subir
* Descripcion: Sube niveles del objeto Heap que hace la llamada
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* i E Indica el nodo en el que nos encontramos
*
*
*
* Valor devuelto:
* void.
*****************************************************************************/
void Heap::Subir(int i)
{
Valor aux;
if((i > 0) && (info[i] > info[(i-1)/2]))
{
aux = info[i];
info[i] = info[(i-1)/2];
info[(i-1)/2] = aux;
Subir((i-1)/2);
}
};
/*****************************************************************************
* Funcion: Bajar
* Descripcion: Baja niveles del objeto Heap que hace la llamada
*
*
*
* Parametros:
*
* Nombre E/S Descripcion
* ------ ----- -----------
* i E Indica el nodo en el que nos encontramos
*
*
*
* Valor devuelto:
* void.
*****************************************************************************/
void Heap::Bajar(int i)
{
int m;
Valor aux;
m = i;
if (2*(i+1)-1 <= num && (info[2*(i+1)-1] > info[m]) )
m = 2*(i+1)-1;
if ( (2*(i+1) < num) && ( info[2*(i+1)]) > info[m])
m = 2*(i+1);
if (m != i)
{
aux = info[i];
info[i] = info[m];
info[m] = aux;
Bajar(m);
}
};