Salve a tutti vorrei sapere come si implementa un min_heap in C++ io ho provato ma mi da eroore in fase di esecuzione mi serve poikè devo testare l'algoritmo mi serve il tempo di esecuzione
questo è il codice in C++ ke ho scritto
heap.h
codice:
typedef int A[];
//length=(int)(sizeof(A[]);
//size=length-1;
int parent(int i);
int left(int i);
int right(int i);
/*
int PARENT(int i);
int LEFT(int i);
int RIGHT(int i);
*/
void Scambia(int Heap, int ind1, int ind2);
void MinHEAPIFY(int Heap, int i,int heapsize_A);
int HEAP_estrai_min(int A[],int l);
void min_heap_insert(int A[], int key,int heapsize_A);
void Diminuisci_chiave(int A[],int i,int k);
void Build_Min_HEAP(int A[],int l);
int MINIMUM(int A[]);
heap.cpp
codice:
#include "hea.h"
#include <stdlib.h>
#include <iostream>
using namespace std;
int NumElementi_Array(int A[]){
return (sizeof(A)/sizeof(A[0]));
}
int NumElementi_Heap(int A[]){
return NumElementi_Array( A) -1;
}
//cout<<"Numero di elementi dell'array: " NumElementi());
int length_array(int A[]){
NumElementi_Array( A);
}
int size_heap(int A[]){
NumElementi_Heap( A);
}
int length(int A[]){
return sizeof A;
}
int heapsize(int A[]){
return length(A) - 1;
}
int length_A;
int heapsiza_A;
int parent(int i){ return i/2; }
int left(int i){ return 2*i; }
int right(int i){ return 2*i+1;}
void scambia(int HEAP[], int ind1, int ind2){
int appo;
appo = HEAP[ind1];
HEAP[ind1]=HEAP[ind2];
HEAP[ind2]=appo;
}
void MinHEAPIFY(int HEAP[], int i,int heapsize_A){
int smallest;
int l = left(i);
int r = right(i);
if ((l <= heapsize_A) && (HEAP[l] < HEAP[i]))
smallest = l;
else
smallest = i;
if ((r <= heapsize_A) && (HEAP[r] < HEAP[smallest]))
smallest = r;
if (smallest != i) {
scambia(HEAP,i,smallest);
MinHEAPIFY(HEAP,smallest,heapsize_A);
}
}
int HEAP_estrai_min(int A[],int l){
int min;
int length_A=l;
int heapsize_A=length_A-1;
if (heapsize_A < 1){
fprintf(stderr,"heap underflow\n");
exit(1);
}
min = A[1];
A[1] = A[heapsize_A];
heapsize_A = (heapsize_A-1);
// size_heap(A)=size;
MinHEAPIFY(A, 1,heapsize_A);
return min;
}
void min_heap_insert(int A[], int key,int heapsize_A){
//int length_A=l;
//int heapsize_A=0;
heapsize_A = (heapsize_A+1);
//cout<< " heapsize : "<< length_A << " \n";
cout<< " heapsize : "<< heapsize_A << " \n";
system("PAUSE");
//size_heap(A)=size;
A[(heapsize_A-1)]=INT_MAX;
Diminuisci_chiave(A,heapsize_A-1, key);
}
int MINIMUM(int A[]) {
return A[1];
}
void Diminuisci_chiave(int A[],int i,int k) {
if(k > A[i]){
fprintf(stderr, "la nuova chiave è più grande di quella corrente.\n");
exit(1);
}
A[i] = k;
while ((i > 1) && (A[parent(i)] > A[i])){
scambia (A,i,parent(i));
i = parent(i);
}
//return i;
}
void Build_Min_HEAP(int A[],int l){
int i;
int length_A=l;
int heapsize_A=length_A;
//size=length_array(A);
// size_heap(A)=size;
for (i =(length_A/2);i>0;i--)
cout<<"heapsize è: " << heapsize_A;
system("PAUSE");
MinHEAPIFY(A, i,heapsize_A);
}
void HEAP_SORT(int A[],int l) {
int i;
int length_A=l;
int heapsize_A=length_A-1;
Build_Min_HEAP(A,l);
for(i=length_A;i>1;i--) {
scambia(A,1,i);
heapsize_A =( heapsize_A-1);
// size_heap(A) = size;
MinHEAPIFY(A,1,heapsize_A);
}
}
main
codice:
#include "hea.h"
#include <iostream>
#include <stdlib.h>
#include <ctime>
#include <cstdlib>
using namespace std;
int main()
{
int* found=NULL;
time_t t1,t2;
clock_t clk1,clk2;
double media=0;
int dim;
int l;
int scelta;
int k;
int length_A,heapsize_A;
do{
cout<<"\n SCEGLI LA FUNZIONE DI CUI VUOI TESTARE LA COMPLESSITA'";
cout<<"\n digita 1 per INSERT";
cout<<"\n digita 2 per SEARCH (ricorsiva)";
cout<<"\n digita 3 per SEARCH (iterativa)";
cout<<"\n digita 4 per uscire dal programma";
cout<<"\n ->";
cin>>scelta;
switch(scelta){
case 1:
cout<<"\n TEST INSERT";
cout<<"\n test di complessita' ";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>l;
length_A=l;
heapsize_A=length_A-1;
int H[length_A];
//Build_Min_HEAP( H);
media=0;
cout<<"\n";
for(int h=0;h<10;h++){
//Crea il vettore di l elementi
for (int i=0;i<l;i++){
//x=new heap_element;
//x->key=rand();
H[i]=rand();
cout<< " la nuova chiave : "<< H[i] << " \n";
cout<< " la vecchia chiave : "<< H[i-1] << " \n";
if(i==0) {
clk1 = clock();
}
min_heap_insert(H, H[i],heapsize_A);
}
clk2 = clock();
cout<<"tempo della "<<h+1<<" prova: ";
double tempo_trascorso = (double)(clk2-clk1)/CLOCKS_PER_SEC;
cout<<tempo_trascorso;
cout<<"\n";
media=media+tempo_trascorso;
}
cout<<"\n media dei tempi -> "<<media/10<<"\n\n";
cout<<"\n\n";
break;
case 2:
cout<<"\n TEST Build_min_heap";
cout<<"\n test di complessita' ";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>l;
length_A=l;
heapsize_A=length_A-1;
H[length_A];
//Crea il vettore di l elementi
for (int i=0;i<l;i++){
H[i]=rand();
cout<< " la nuova chiave : "<< H[i] << " \n";
cout<< " la vecchia chiave : "<< H[i-1] << " \n";
system("PAUSE");
}
// media=0;
cout<<"\n";
// for(int h=0;h<10;h++){
clk1 = clock();
Build_Min_HEAP( H,l);
//HEAP_SORT( H);
clk2 = clock();
// cout<<"tempo della "<<h+1<<" prova: ";
cout<<"tempo della prova: ";
double tempo_trascorso;
tempo_trascorso = (double)(clk2-clk1)/CLOCKS_PER_SEC;
cout<<tempo_trascorso;
cout<<"\n";
// media=media+tempo_trascorso;
// }
//cout<<"\n media dei tempi -> "<<media/10<<"\n\n";
cout<<"\n\n";
break;
case 3:
cout<<"\n TEST SEARCH_min";
cout<<"\n test di complessita' ";
cout<<"\n inserisci la dimensione dell'input ->";
cin>>l;
length_A=l;
heapsize_A=length_A-1;
H[length_A];
//Crea il vettore di l elementi
for (int i=0;i<l;i++){
H[i]=rand();
// min_heap_insert(H, H->h[i].key);
}
Build_Min_HEAP( H,l);
media=0;
for(int h=0;h<10;h++){
clk1 = clock();
int min=MINIMUM(H);
clk2 = clock();
cout<<"tempo della "<<h+1<<" prova: ";
double tempo_trascorso = (double)(clk2-clk1)/CLOCKS_PER_SEC;
cout<<tempo_trascorso;
cout<<"\n";
media=media+tempo_trascorso;
}
cout<<"\n media dei tempi -> "<<media/10<<"\n\n";
cout<<"\n\n";
break;
case 4:
exit(0);
break;
}
}while((scelta>0)&&(scelta<5));
cout<<"\n Errore di digitazione \n";
cout<<"\n\n\n\n\n";
system("PAUSE");
}
potreste aiutarmi
GRazie
Permessi di invio
