#define max 10 using namespace std




Yüklə 11.06 Kb.
tarix28.02.2016
ölçüsü11.06 Kb.
#include

#include

#define MAX 10

using namespace std;

typedef int Base;

typedef struct Elemento

{ int pr;

Base info;

};

typedef Elemento Vector[MAX];



// Interfaz

class Heap

{ private:

Vector v;

int u;

void Subir();



void Bajar();

public:


Heap();

bool Vacio();

void Agregar(Elemento);

Elemento Extraer();

};

// Implementacion



Heap::Heap()

{ cout << "Creando heap" << endl << endl;

u = 0;

}

bool Heap::Vacio()



{ return (u == 0); }

void Heap::Subir()

{ int k, i;

Elemento x;

x.pr = v[u].pr;

x.info = v[u].info;

v[0].pr = v[u].pr;

v[0].info = v[u].info;

i = u;

k = i/2;


while (v[k].pr > x.pr)

{ v[i].pr = v[k].pr;

v[i].info = v[k].info;

i = k;


k = i/2;

};

v[i].pr = x.pr;



v[i].info = x.info;

}

void Heap::Bajar()



{ int k, i, fin=0;

Elemento x;

x.pr = v[1].pr;

x.info = v[1].info;

k = 1;

i = k*2;


while (k <= u/2 && !fin)

{ if (i < u)

if (v[i+1].pr < v[i].pr)

i = i+1;


if (x.pr > v[i].pr)

{ v[k].pr = v[i].pr;

v[k].info = v[i].info;

k = i;


i = k*2;

}

else fin = 1;



}

v[k].pr = x.pr;

v[k].info = x.info;

}

void Heap::Agregar(Elemento e)



{ u++;

v[u].pr = e.pr;

v[u].info = e.info;

Subir();


}

Elemento Heap::Extraer()

{ //Base x = v[1].info;

Elemento e = v[1];

v[1].pr = v[u].pr;

v[1].info = v[u].info;

u--;

Bajar();


return e;

}

// Despliegue de contenido



void Imprime(Heap &H)

{ Elemento e;

Heap C;

while(!H.Vacio())



{ e = H.Extraer();

cout << "Prioridad: " << e.pr << endl;

cout << "Valor info: " << e.info << endl;

C.Agregar(e);

cout << endl;

}

while(!C.Vacio())



H.Agregar(C.Extraer());

}

// Creación de un Heap



void CrearHeap(Heap &H)

{ Elemento e;

int k;

cout << "Ingrese un entero:" << endl;



cin >> k;

while(k != 0) {

e.pr = k;

e.info = k+1;

H.Agregar(e);

cout << "Ingrese un entero:" << endl;

cin >> k;

}

}



// Funcion main

int main(int argc, char *argv[])

{ Heap H;

CrearHeap(H);

Imprime(H);

system("PAUSE");



return EXIT_SUCCESS;

}


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə