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

#include 

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;}
		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, def. 100 
		~Heap ();
		void Insert (int e);
		int Maximum ();
		void ExtractMaximum ();
		friend void ShowHeap (Heap* h);
};

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

Heap::~Heap()
{
	delete [] heap_array;
}

void exchange (int& n, int& m)
{
	int temp;
	
	temp = n;
	n = m;
	m = temp;
}


void Heap::Insert (int e)
{
	int i, Parent_i;

	if (heap_size < size) {
		i = heap_size++;
		heap_array[i] = e;
		Parent_i = Parent(i);
		while ((i > 0) && (heap_array[Parent_i] < heap_array[i])) {
			exchange(heap_array[i], heap_array[Parent_i]);
			i = Parent_i;
			Parent_i = Parent(i);
			// ShowHeap (this);
		}
		heap_array[i] = e;
	} else cout << "Insert: heap is full\n";
}

int Heap::Maximum ()
{
	if (heap_size > 0) return heap_array[0];
	else {cout << "Maximum: heap is empty" << endl; 
              return 0;
        }
}


void Heap::Heapify (int i)
{
	int largest, Left_i, Right_i;

	if ((Left_i = Left(i)) > heap_size-1) Left_i = i;  // Left(i) fuori range
	if ((Right_i = Right(i)) > heap_size-1) Right_i = i; // Right(i) fuori range

	largest = i;
	if (heap_array[largest] < heap_array[Left_i]) largest = Left_i;
	if (heap_array[largest] < heap_array[Right_i]) largest = Right_i;
	// largest e' l'indice del massimo tra heap_array[i], heap_array[Left_i],
	// heap_array[Right_i]

	if (i != largest) {
		exchange(heap_array[i], heap_array[largest]);
		Heapify(largest);
	}
}

void Heap::ExtractMaximum ()
{
	if (heap_size > 0) {
		heap_array[0] = heap_array[heap_size-1];
		heap_size--;
		// ShowHeap(this);
		Heapify(0);
	} else cout << "ExtractMaximum: heap is empty\n";
}


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

int main (void)
{
	cout << "Heap in C++" << endl;
	Heap hp;
	
	hp.Insert(16); // ShowHeap(&hp);
	hp.Insert(7);  // ShowHeap(&hp);
	hp.Insert(14); // ShowHeap(&hp);
	hp.Insert(9);  // ShowHeap(&hp);
	hp.Insert(1);  // ShowHeap(&hp);
	hp.Insert(8);  // ShowHeap(&hp);
	hp.Insert(10);
	hp.Insert(3);
	hp.Insert(2);
	hp.Insert(4); ShowHeap(&hp);

	hp.Insert(15);
	ShowHeap(&hp);
	
	hp.ExtractMaximum(); ShowHeap(&hp);
	

	return 0;
}

// eof