[C++] Heap

[robs05]

Salve ragazzi,

ho implementato in c++ un heap utilizzato prima come algoritmo di orinamento ( heapsort) e poi stavo implementanto le procedure per renderlo coda di priorità.

In effetti ho implementato

void max_heapify(int A[], int heap_size, int i);
void build_max_heap(int A[],int heap_size);
void heap_sort(int A[], int heap_size);
int heap_maximum(int A[]);
int heap_extract_max(int A[], int &heap_size);
void heap_increase_key(int A[],int i, int key);
void max_heap_insert(int A[],int &heap_size, int key);

il problema o meglio l'errore logico che incontro è quando chiamo la procedura
max_heap_insert

void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size = heap_size + 1 ;
	A[++heap_size] = -10000;
	heap_increase_key(A,heap_size,key);
}

che chiama la procedura heap_increase_key che funziona correttamente

void heap_increase_key(int A[],int i, int key)
{
	if( key < A[i] )
	{
		cerr << "La nuova chiave è più piccola di quella corrente" << endl;
		return;
	}

	A[i] = key;

	while( (i > 1) && (A[parent(i)] < A[i] ) )
	{
		swap(A[i],A[parent(i)]);
		i = parent(i);
	}

}

Allora io creo un array con numeri casuali
applico build_max_heap(A,heap_size);
e quindi costruisco l'heap

a(1) a(2) a(3) (a4) ...... a(n)

poi applico max_heap_insert(A,heap_size,101);

e giustamente l'output desiderato deve essere questo

a(1)=101 a(2) a(3) (a4) ...... a(n)...a(n+1)=numero che è sceso nella foglia e che soddisfi ancora le proprietà dell'heap

invece l'output che ottengo è:

a(1)=101 a(2) a(3) (a4) ...... a(n)...a(n+1)=-858993460 a(n+2)= numero che è sceso nella foglia e che soddisfi ancora le proprietà dell'heap

c'è qualcuno che gentilmente potrebbe dare un occhiata e potrebbe aiutarmi a trovare quest'errore logico. grazie mille

saluti

[Vincenzo1968]

Originariamente inviato da robs05

Salve ragazzi,
...
il problema o meglio l'errore logico che incontro è quando chiamo la procedura
max_heap_insert

void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size = heap_size + 1 ;
	A[++heap_size] = -10000;
	heap_increase_key(A,heap_size,key);
}

...

Ciao,

incrementi due volte heap_size. Prova così:

void max_heap_insert(int A[],int &heap_size, int key)
{
	A[++heap_size] = -10000;
	heap_increase_key(A,heap_size,key);
}

o così:

void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size = heap_size + 1;
	A[heap_size] = -10000;
	heap_increase_key(A,heap_size,key);
}

o così:

void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size += 1;
	A[heap_size] = -10000;
	heap_increase_key(A,heap_size,key);
}

[robs05]

ciao

in effetti il codice che dava l'errore è proprio questo

void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size = heap_size + 1;
	A[heap_size] = -10000;
	heap_increase_key(A,heap_size,key);
}

è stato un errore di copia nel thread

effettuando varie prove prima con il postincremento e poi con il preincremento ho dimenticato di aggiornare il codice alla versione originale che mi dava l'errore, ti ringrazio cmq ma mi sa che si dovrà sbattere ancora un pò la testa

[robs05]

ciao

in effetti il codice che dava l'errore è proprio questo

void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size = heap_size + 1;
	A[heap_size] = -10000;
	heap_increase_key(A,heap_size,key);
}

è stato un errore di copia nel thread

effettuando varie prove prima con il postincremento e poi con il preincremento ho dimenticato di aggiornare il codice alla versione originale che mi dava l'errore, ti ringrazio cmq ma mi sa che si dovrà sbattere ancora un pò la testa

[Vincenzo1968]

A questo punto l'errore dovrebbe trovarsi un qualche altro punto del codice. Così com'è, la funzione è implementata come consiglia il Cormen. È un problema, per te, postare l'intero codice?

Ciao

[robs05]

no nessun problema, solo che adesso su questo calcolatore non ho il codice a disposizione...appena possibile lo posto

[robs05]

ecco il codice:

questo è il file header function.h

void print_array(int a[], int heap_size);
void copia_array( int a[], int b[], int heap_size);
void carica_array(int a[], int heap_size);
void swap(int &a, int &b);

int parent(int i);
int left( int i );
int right( int i );

void max_heapify(int A[], int &heap_size, int i);
void build_max_heap(int A[],int &heap_size);
void heap_sort(int A[], int heap_size);
int heap_maximum(int A[]);
int heap_extract_max(int A[], int &heap_size);
void heap_increase_key(int A[],int i, int key);
void max_heap_insert(int A[],int &heap_size, int key);


void max_heap_test(int A[], int heap_size);

questo è il file function.cpp

#include <iostream>
using namespace std;


#include "function.h"


int heap_maximum(int A[])
{
	return A[1];
}

int heap_extract_max(int A[], int &heap_size)
{
	int max;
	if (heap_size < 1)
	{
		cerr << "Underflow dell'heap";
		return 0;
	}

	max = A[1];
	A[1]=A[heap_size - 1];
	heap_size--;
	
	max_heapify(A,heap_size,1);
	return max;
}


void heap_increase_key(int A[],int i, int key)
{
	if( key < A[i] )
	{
		cerr << "La nuova chiave e' piu' piccola di quella corrente" << endl;
		return;
	}

	A[i] = key;

	while( (i > 1) && (A[parent(i)] < A[i] ) )
	{
		swap(A[i],A[parent(i)]);
		i = parent(i);
	}

}


void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size = heap_size + 1 ;
	A[heap_size] = -10000;
	heap_increase_key(A,heap_size,key);
}

void max_heapify(int A[], int &heap_size, int i)
{
	int l = left(i);
	int r = right(i);
	int massimo;

	if( l <= heap_size  &&  A[l] > A[i] )
		massimo = l;
	else
		massimo = i;

	if( r <=heap_size  &&  A[r] > A[massimo])
		massimo = r;

	if( massimo != i )
	{
		swap(A[i],A[massimo]);
		max_heapify(A,heap_size,massimo);
	}
}


void build_max_heap(int A[],int &heap_size)
{
	for(int i = (heap_size-1)/2; i > 0; i-- )
		max_heapify(A,heap_size,i);
}

void heap_sort(int A[], int heap_size)
{
	int size_heap = heap_size - 1;
	build_max_heap(A,heap_size);

	for( int i = heap_size - 1; i >= 2 ; i-- )
	{
		swap(A[1],A[i]);
		size_heap = size_heap - 1;
		max_heapify(A,size_heap,1);
	}
}



void max_heap_test(int A[], int heap_size)
{
	int test = 1;
	for(int i = 2; i < heap_size; i++ )
	      if (A[parent(i)] >= A[i])
			  test++;
	if( test == heap_size-1 )  
		cout << "OK-> L' array e' un max heap" << endl;
	else
		cout << "NO-> L'array non e' un max heap" << endl;



}



void swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}


void carica_array(int a[], int heap_size)
{
	for(int i = 1; i < heap_size; i++)
		a[i] = rand()%100;
}


void copia_array( int a[], int b[], int heap_size)
{
	for(int i = 1; i < heap_size; i++)
		b[i] = a[i];
	
}
void print_array(int a[], int heap_size)
{
	for(int i = 1; i < heap_size ; i++)
	{
		if( (i != 0) && (i%20) == 0 ){ cout << endl; }
		cout << a[ i ] << " ";
	}
	cout << endl;

}


int parent(int i)
{
	return i/2;	
}

int left( int i )
{
	return 2*i;
}

int right( int i )
{
	return 2*i + 1;
}

questo è il main main.cpp

#include <iostream>
using namespace std;
#include <time.h>
#include "function.h"

const int array_size = 100;



int main()
{
	srand(time(NULL));
	int heap_size = 11;


	int A[array_size];

	carica_array(A,heap_size);
	cout << "\nArray generico.... " << endl;
	print_array(A,heap_size);
	//coustrisci max-heap
	build_max_heap(A,heap_size);
	//heap_sort(A,heap_size);
	cout << "\nHeap ...." << endl;
	print_array(A,heap_size);
	cout << "\nheap size --> " << heap_size << endl;
	//cout << heap_maximum(A) << endl;
	//cout << heap_extract_max(A,heap_size) << endl;
	//heap_increase_key(A,10,10);
	cout << "\nInserisco elemento 101" << endl;
	max_heap_insert(A,heap_size,101);

	//max_heap_insert(A,heap_size,102);
	//max_heap_insert(A,heap_size,103);
	cout << "\nheap size --> " << heap_size << endl;

	cout << "\nA[11] =  " << A[11] << endl;
	cout << "\nA[12] =  " << A[12] << endl;

	print_array(A,heap_size);





	max_heap_test(A,heap_size);


	return 0;
}

[Vincenzo1968]

Nel Cormen gli esempi sono fatti su array in base 1. Bisogna adattarli agli array del C/C++ che sono invece in base 0.
Per esempio, le funzioni parent, left e right diventano:

int parent(int i)
{
	return i/(2+1);	
}

int left( int i )
{
	return 2*i + 1;
}

int right( int i )
{
	return 2*i + 2;
}

File funzioni.cpp:

#include <iostream>
using namespace std;

#include "function.h"

int heap_maximum(int A[])
{
	return A[0];
}

int heap_extract_max(int A[], int &heap_size)
{
	int max;
	if (heap_size < 1)
	{
		cerr << "Underflow dell'heap";
		return 0;
	}

	max = A[0];
	A[0]=A[heap_size - 1];
	heap_size--;
	
	max_heapify(A,heap_size,0);
	return max;
}

void heap_increase_key(int A[],int i, int key)
{
	if( key < A[i] )
	{
		cerr << "La nuova chiave e' piu' piccola di quella corrente" << endl;
		return;
	}

	A[i] = key;

	while( (i > 0) && (A[parent(i)] < A[i] ) )
	{
		swap(A[i],A[parent(i)]);
		i = parent(i);
	}

}

void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size = heap_size + 1;
	A[heap_size - 1] = -10000;
	heap_increase_key(A,heap_size-1,key);
}

void max_heapify(int A[], int &heap_size, int i)
{
	int l = left(i);
	int r = right(i);
	int massimo;

	if( l < heap_size  &&  A[l] > A[i] )
		massimo = l;
	else
		massimo = i;

	if( r < heap_size  &&  A[r] > A[massimo])
		massimo = r;

	if( massimo != i )
	{
		swap(A[i],A[massimo]);
		max_heapify(A,heap_size,massimo);
	}
}

void build_max_heap(int A[],int &heap_size)
{
	for(int i = heap_size/2; i >= 0; i-- )
		max_heapify(A,heap_size,i);
}

void heap_sort(int A[], int heap_size)
{
	build_max_heap(A, heap_size);

	for( int i = heap_size - 1; i >= 1 ; i-- )
	{
		swap(A[0], A[i]);
		heap_size = heap_size - 1;
		max_heapify(A, heap_size, 0);
	}
}

void max_heap_test(int A[], int heap_size)
{
	int test = 0;
	for(int i = 1; i < heap_size; i++ )
	      if (A[parent(i)] >= A[i])
			  test++;
	if( test == heap_size-1 )  
		cout << "OK-> L' array e' un max heap" << endl;
	else
		cout << "NO-> L'array non e' un max heap" << endl;
}

void swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

void carica_array(int a[], int heap_size)
{
	for(int i = 0; i < heap_size; i++)
		a[i] = rand()%100;
}

void copia_array( int a[], int b[], int heap_size)
{
	for(int i = 0; i < heap_size; i++)
		b[i] = a[i];
	
}
void print_array(int a[], int heap_size)
{
	for(int i = 0; i < heap_size; i++)
	{
		if( (i != 0) && (i%20) == 0 ){ cout << endl; }
		cout << a[ i ] << " ";
	}
	cout << endl;
}

int parent(int i)
{
	return i/(2+1);	
}

int left( int i )
{
	return 2*i + 1;
}

int right( int i )
{
	return 2*i + 2;
}

File main.cpp:

#include <iostream>
using namespace std;
#include <time.h>
#include "function.h"

const int array_size = 100;

int main()
{
	srand(time(NULL));
	int heap_size = 11;

	int A[array_size];

	carica_array(A,heap_size);
	cout << "\nArray generico.... " << endl;
	print_array(A,heap_size);

	//coustrisci max-heap
	build_max_heap(A,heap_size);
	//heap_sort(A,heap_size);
	cout << "\nHeap ...." << endl;
	print_array(A,heap_size);
	cout << "\nheap size --> " << heap_size << endl;
	cout << "heap maximum -> " << heap_maximum(A) << endl;
	//cout << heap_extract_max(A,heap_size) << endl;
	//heap_increase_key(A,10,10);
	cout << "\nInserisco elemento 101" << endl;
	max_heap_insert(A,heap_size,101);

	//max_heap_insert(A,heap_size,102);
	//max_heap_insert(A,heap_size,103);
	cout << "\nheap size --> " << heap_size << endl;
	cout << "heap maximum -> " << heap_maximum(A) << endl;

	cout << "\nA[0] =  " << A[0] << endl;

	cout << "\nA[" << heap_size - 2 << "] =  " << A[heap_size - 2] << endl;
	cout << "\nA[" << heap_size - 1 << "] =  " << A[heap_size - 1] << endl;

	cout << endl;

	print_array(A,heap_size);

	max_heap_test(A,heap_size);

	return 0;
}

[Vincenzo1968]

Ho dato un'occhiata alle varie implementazioni sul web e ho visto che è conveniente mantenere gli array con indici in base 1:

File function.h:

#ifndef HEAP_H
#define HEAP_H

void print_array(int a[], int heap_size);
void copia_array( int a[], int b[], int heap_size);
void carica_array(int a[], int heap_size);
void swap(int &a, int &b);

int parent(int i);
int left(int i);
int right(int i);

void max_heapify(int A[], int heap_size, int i);
void build_max_heap(int A[],int heap_size);
void heap_sort(int A[], int heap_size);
int heap_maximum(int A[]);
int heap_extract_max(int A[], int &heap_size);
void heap_increase_key(int A[],int i, int key);
void max_heap_insert(int A[],int &heap_size, int key);

void max_heap_test(int A[], int heap_size);

#endif // HEAP_H

File function.cpp:

#include <iostream>
using namespace std;

#include "function.h"

int heap_maximum(int A[])
{
	return A[1];
}

int heap_extract_max(int A[], int &heap_size)
{
	int max;
	if (heap_size < 1)
	{
		cerr << "Underflow dell'heap";
		return 0;
	}

	max = A[1];
	A[1] = A[heap_size];
	heap_size--;
	
	max_heapify(A, heap_size, 1);

	return max;
}

void heap_increase_key(int A[], int i, int key)
{
	if( key < A[i] )
	{
		cerr << "La nuova chiave e' piu' piccola di quella corrente" << endl;
		return;
	}

	A[i] = key;

	while( (i > 1) && (A[parent(i)] < A[i] ) )
	{
		swap(A[i], A[parent(i)]);
		i = parent(i);
	}
}

void max_heap_insert(int A[],int &heap_size, int key)
{
	heap_size = heap_size + 1;
	A[heap_size] = -10000;
	heap_increase_key(A, heap_size, key);
}

void max_heapify(int A[], int heap_size, int i)
{
	int l = left(i);
	int r = right(i);
	int massimo;

	if( l <= heap_size  &&  A[l] > A[i] )
		massimo = l;
	else
		massimo = i;

	if( r <= heap_size  &&  A[r] > A[massimo])
		massimo = r;

	if( massimo != i )
	{
		swap(A[i], A[massimo]);
		max_heapify(A, heap_size, massimo);
	}
}

void build_max_heap(int A[], int heap_size)
{
	for(int i = heap_size/2; i >= 1; i-- )
		max_heapify(A, heap_size, i);
}

void heap_sort(int A[], int heap_size)
{
	build_max_heap(A, heap_size);

	for( int i = heap_size; i >= 2 ; i-- )
	{
		swap(A[1], A[i]);
		heap_size = heap_size - 1;
		max_heapify(A, heap_size, 1);
	}
}

void max_heap_test(int A[], int heap_size)
{
	int test = 0;
	for(int i = 1; i <= heap_size; i++ )
	      if (A[parent(i)] >= A[i])
			  test++;
	if( test == heap_size )  
		cout << "OK-> L' array e' un max heap" << endl;
	else
		cout << "NO-> L'array non e' un max heap" << endl;
}

void swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}

void carica_array(int a[], int heap_size)
{
	for(int i = 1; i <= heap_size; i++)
		a[i] = rand()%100;

	/*
	a[1] = 4;
	a[2] = 1;
	a[3] = 3;
	a[4] = 2;
	a[5] = 16;
	a[6] = 9;
	a[7] = 10;
	a[8] = 14;
	a[9] = 8;
	a[10] = 7;
	*/
}

void copia_array( int a[], int b[], int heap_size)
{
	for(int i = 1; i <= heap_size; i++)
		b[i] = a[i];
	
}
void print_array(int a[], int heap_size)
{
	for(int i = 1; i <= heap_size; i++)
	{
		if( (i != 0) && (i%20) == 0 ){ cout << endl; }
		cout << a[ i ] << " ";
	}
	cout << endl;
}

int parent(int i)
{
	return i/2;	
}

int left( int i )
{
	return 2*i;
}

int right( int i )
{
	return 2*i + 1;
}

File main.cpp:

#include <iostream>
using namespace std;
#include <time.h>
#include "function.h"

const int array_size = 100;

int main()
{
	srand(time(NULL));
	int heap_size = 10;

	int A[array_size];

	carica_array(A,heap_size);
	cout << "\nArray generico.... " << endl;
	print_array(A,heap_size);

	//coustrisci max-heap
	build_max_heap(A,heap_size);
	//heap_sort(A,heap_size);
	cout << "\nHeap ...." << endl;
	print_array(A,heap_size);


	int x = 5;
	cout << endl;
	cout << "parent(" << x << ") -> " << parent(x) << endl;


	cout << "\nheap size --> " << heap_size << endl;
	cout << "heap maximum -> " << heap_maximum(A) << endl;
	//cout << heap_extract_max(A,heap_size) << endl;
	//heap_increase_key(A,10,10);
	cout << "\nInserisco elemento 101" << endl;
	max_heap_insert(A,heap_size,101);

	//max_heap_insert(A,heap_size,102);
	//max_heap_insert(A,heap_size,103);
	cout << "\nheap size --> " << heap_size << endl;
	cout << "heap maximum -> " << heap_maximum(A) << endl;

	cout << "\nA[0] =  " << A[0] << endl;

	cout << "\nA[" << heap_size - 2 << "] =  " << A[heap_size - 2] << endl;
	cout << "\nA[" << heap_size - 1 << "] =  " << A[heap_size - 1] << endl;

	cout << endl;

	print_array(A,heap_size);

	max_heap_test(A,heap_size);

	cout << endl << "array ordinato: " << endl;
	heap_sort(A, heap_size);
	print_array(A,heap_size);

	return 0;
}

[robs05]

ok grazie tutto funziona solo correttamente adesso mi guardo il codice per bene e capisco come creare un heap con base array 0, l'unica cosa che volevo chiarire è il perchè nel file header ed in questi due prototipi manca il passaggio del parametro heap_size per riferimento

void max_heapify(int A[], int heap_size, int i);
void build_max_heap(int A[],int heap_size);

all'atto della compilazione mi segnala l'errore in quanto viene interpretata dal compilatore come un overload

modificando cos'

void max_heapify(int A[], int &heap_size, int i);
void build_max_heap(int A[],int &heap_size);

tutto funziona correttamente.

penso sia un errore di copia...altrimenti se non è cosi non sono riuscito a capire il perchè

grazie

[Vincenzo1968]

Originariamente inviato da robs05

ok grazie tutto funziona solo correttamente adesso mi guardo il codice per bene e capisco come creare un heap con base array 0, l'unica cosa che volevo chiarire è il perchè nel file header ed in questi due prototipi manca il passaggio del parametro heap_size per riferimento

void max_heapify(int A[], int heap_size, int i);
void build_max_heap(int A[],int heap_size);

all'atto della compilazione mi segnala l'errore in quanto viene interpretata dal compilatore come un overload

modificando cos'

void max_heapify(int A[], int &heap_size, int i);
void build_max_heap(int A[],int &heap_size);

tutto funziona correttamente.

penso sia un errore di copia...altrimenti se non è cosi non sono riuscito a capire il perchè

grazie

Ciao Robs,
ti consiglio di lasciar perdere la versione con array in base 0. Utilizza quella che ho postato per ultima.

Il compilatore da errore perché devi modificare anche la dichiarazione delle due funzioni nel file header. Poiché le due funzioni non modificano il valore di heap_size, ho pensato di togliere il riferimento e passare l'argomento per valore. Ma funziona in entrambi i casi.

Ora che hai una versione funzionante, potresti provare a incapsulare il tutto in una classe template in modo da gestire agevolmente differenti tipi di dati.

Ciao

[robs05]

ah ecco erano due versioni di codice, dato la troppa lunghezza del post non avevo notato alle diversità... scusami.

cmq grazie mille adesso mi è tutto chiaro, in effetti ho iniziato ad implementare il tutto ragionando con array di base 1 poi non so il perchè iteravo fino a heap_size - 1.

ps.:se non chiedo troppo dato che prima si è fatto riferimento al Cormen ed io sono uno studente che in effetti sta adottando quel testo, le volevo chiedere se gentilmente ha qualche link da postarmi concerne qualche dispensa o qualche approfondimenti ricchi di esempi delle equazioni di ricorrenza (Cap 4) ed i vari metodi per risolverle.

saluti

[Vincenzo1968]

Originariamente inviato da robs05

ah ecco erano due versioni di codice, dato la troppa lunghezza del post non avevo notato alle diversità... scusami.

cmq grazie mille adesso mi è tutto chiaro, in effetti ho iniziato ad implementare il tutto ragionando con array di base 1 poi non so il perchè iteravo fino a heap_size - 1.

ps.:se non chiedo troppo dato che prima si è fatto riferimento al Cormen ed io sono uno studente che in effetti sta adottando quel testo, le volevo chiedere se gentilmente ha qualche link da postarmi concerne qualche dispensa o qualche approfondimenti ricchi di esempi delle equazioni di ricorrenza (Cap 4) ed i vari metodi per risolverle.

saluti

Se mi dai dal tu è meglio, lo preferisco. Purtroppo non ti posso aiutare sulle equazioni di ricorrenza ché di matematica ne so poco e niente. Anzi, mi associo alla tua richiesta. Speriamo che qualcuno fornisca quei link.

Ciao

[robs05]

ok allora speriamo che qualcuno possa soddisfare questa richiesta

ciao e di nuovo grazie

[Vincenzo1968]

Originariamente inviato da robs05

...
ps.:se non chiedo troppo dato che prima si è fatto riferimento al Cormen ed io sono uno studente che in effetti sta adottando quel testo, le volevo chiedere se gentilmente ha qualche link da postarmi concerne qualche dispensa o qualche approfondimenti ricchi di esempi delle equazioni di ricorrenza (Cap 4) ed i vari metodi per risolverle.

saluti

Ho trovato questo:

http://www.educ.di.unito.it/~albano/...nse/MatDis.pdf