////////////////////////////////////////////////////////////////////
//  Sýnislausn á Dæmi 5 á Vikublaði 13 í Tölvunarfræði 2
//
//  Hjálmtýr Hafsteinsson, apríl 2005
////////////////////////////////////////////////////////////////////
#include <stdlib.h>
#include <iostream.h>
#include <time.h>


// Útfærsla á forgangsbiðröð með hrúgu með viðbótaraðferðinni replaceMax
template <class Item>
class PQ
{
	private:
		Item *pq; 
		int N;
		void exch(Item &A, Item &B) 
			{ Item t = A; A = B; B = t; } 
		void fixUp(Item a[], int k)
		{
			while (k > 1 && a[k/2] < a[k]) {
				exch(a[k], a[k/2]);
				k = k/2;
			}
		}
		void fixDown(Item a[], int k, int N)
		{
			while (2*k <= N) {
				int j = 2*k;
				if (j < N && a[j] < a[j+1]) j++;
				if (!(a[k] < a[j])) break;
				exch(a[k], a[j]); k = j;
			}
		}
	public:
		PQ(int maxN)
			{ pq = new Item[maxN+1]; N = 0; }
		int empty() const
			{ return N == 0; }
		void insert(Item v)
			{ pq[++N] = v; fixUp(pq, N); }
		Item getmax()
		{ 
			exch(pq[1], pq[N]); 
			fixDown(pq, 1, N-1); 
			return pq[N--]; 
		}
		Item replaceMax( Item v )
		{
			exch( pq[1], v );
			fixDown( pq, 1, N );
			return v;
		}
};


// Prófunarforrit til að bera saman hraða mism. útfærsla
int main()
{
    int i;
    PQ<int> fb(100);

	// Upphafsstilla slembitölugjafa...
	srand( (unsigned)time( NULL ) );

	// Setja inn 10 stök...
	for( i=0; i<10; i++ ) {
		int st = rand() % 100;
		fb.insert( st );
		cout << st << ", ";
	}
	cout << endl;

	// Skipta um stærsta...
	cout << "Settum 40 i stad " << fb.replaceMax( 40 ) << endl;

	// Hvað er nú stærst?
	cout << "Nu er staerst: " << fb.getmax() << endl;

    return 0;
}