Code di Prirità

datatype PriorityQueue, Element;
constructors: EmptyQueue: PriorityQueue
	Insert: PriorityQueue, Element -> PriorityQueue
	ExtractMaximum: PriorityQueue -> PriorityQueue
observations:
	Maximum: PriorityQueue -> Element
semantics:
	Insert(S,x) = S unione {x}
	Maximum(S) = x tale che Priorità(x) =
			        max {Priorità(y)| y in S}
	ExtractMaximum(S) = S \ {Maximum(S)}

/* Heaps in C++: realizzazione non parametrica */

#include <iostream.h>

class Heap {
	private:
		int   size;		// dimensione del vettore heap_array
		int   heap_size;	// prossima loc libera sul vettore
		int*  heap_array;
		inline int   Left (int i) {return 2*i + 1;} // i vettori in C/C++ cominciano da 0
		inline int   Right (int i) {return 2*i + 2;}
		inline int   Parent (int i) {return (i+1)/2 - 1;}
		void Heapify (int i);
	public:
		Heap (int hs = 100); // hs heap dimensione max, default = 100 
		~Heap ();  // distruttore (opera la deallocazione di uno heap)
		void Insert (int e);
		int Maximum ();
		void ExtractMaximum ();
		friend void ShowHeap (Heap* h); // friend: funzione che non e' membro della classe
		                                // ma che puo' accedere ai suoi membri privati
};

Heap::Heap(int hs)
{
	size = hs;
	heap_size = 0;
	heap_array = new int [hs];
}

Heap::~Heap()
{
	delete [] heap_array;  // sintassi per deallocare un vettore allocato con new
}

void exchange (int& n, int& m) // int& n e' analogo del Pascal var n
{
	int temp;
	
	temp = n;
	n = m;
	m = temp;
}


void Heap::Insert (int e)
{
    int i, Parent_i;  // i e' l'indice dell'elemento corrente (all'inizio una foglia)
                      // Parent_i = Parent(i) (per risparmiare chiamate e divisioni)

	if (heap_size < size) {
		...
		// ShowHeap (this);  sintassi da usare se si vuole una stampa dello heap qui per il debugging
	} else cout << "Insert: heap is full\n"; // invia la stringa allo stream di output
}

int Heap::Maximum ()
{
	...
}


void Heap::Heapify (int i)
// pre: Left(i), Right(i) sono radici di heap;
// post: i e' radice di uno heap
{
	int largest, Left_i, Right_i; 
	// Left_i = Left(i), Right_i = Right(i) per ragioni di efficienza;
	// largest e' usata per memorizzare l'indice del massimo
	// tra heap_array[i], heap_array[Left_i], heap_array[Right_i]
	...
}

void Heap::ExtractMaximum ()
{
	...
}

/* funzione di utilita' */

void ShowHeap (Heap* h)
{
	for (int i = 0; i < h->heap_size; i++)
		cout << h->heap_array[i] << " ";
	cout <<endl;
}

/* Main di prova */

int main (void)
{
	cout << "Heap in C++" << endl;
	Heap hp;

	
	hp.Insert(16);
	hp.Insert(7);
	hp.Insert(14);
	hp.Insert(1); 
	hp.Insert(8);
	hp.Insert(10);
	hp.Insert(3);
	hp.Insert(2);
	hp.Insert(4);
	hp.Insert(15);
	ShowHeap(&hp);
	
	hp.ExtractMaximum(); 
	ShowHeap(&hp);

	return 0;
}

HeapSort