////////////////////////////////////////////////////////////////////
//  Sýnislausn á Dæmi 5 á Vikublaði 14 í Tölvunarfræði 2
//
//  Berum saman hæð tvíleitartrés eftir því í hvaða röð
//   inntaksstökin eru.
//
//  Hjálmtýr Hafsteinsson, apríl 2005
////////////////////////////////////////////////////////////////////
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;


static int maxKey = 1000;
typedef int Key;
class Item 
  { 
    private:
      Key keyval; 
      float info;
    public:
      Item() 
        { keyval = maxKey; } 
	  Item( Key k, float i ) : keyval(k), info(i) {}
      Key key()
        { return keyval; }
      int null()
        { return keyval == maxKey; }
      void rand()
        { keyval = 1000*::rand()/RAND_MAX;   
          info = 1.0*::rand()/RAND_MAX; }  
      int scan(istream& is = cin)
        { return (is >> keyval >> info) != 0; }
      void show(ostream& os = cout)
        { os << keyval << " " << info << endl; }
   }; 

ostream& operator<<(ostream& os, Item& x)
  { x.show(os); return os; }


template <class Item>
Item max( Item A, Item B )
{
	if( A > B ) return A;
	return B;
}

template <class Item>
void exch(Item &A, Item &B) 
{
	Item t = A;
	A = B;
	B = t;
} 

template <class Item>
inline void fixUp(Item a[], int k)
{
	while (k > 1 && a[k/2] < a[k]) {
		exch(a[k], a[k/2]);
		k = k/2;
	}
}

template <class Item>
inline 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;
	}
}


// Hrúgu-útfærsla á forgangsbiðröð með viðbótaraðferð til að ná beint í stök fylkisins
template <class Item>
class PQ
{
	private:
		Item *pq; 
		int N;
	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 get( int i )			// Ný aðferð til að ná í stök pq fylkisins
			{ return pq[i]; }
};


// Útfærsla á tvíleitartré úr kennslubók með viðbótaraðferðinni height
template <class Item, class Key>
class ST 
  {
    private:
      struct node 
        { Item item; node *l, *r;
          node(Item x)
            { item = x; l = 0; r = 0; } 
        }; 
      typedef node *link;
      link head;
      Item nullItem;
      Item searchR(link h, Key v)
        { if (h == 0) return nullItem;
          Key t = h->item.key();
          if (v == t) return h->item;
          if (v < t) return searchR(h->l, v);
                else return searchR(h->r, v);
        }
      void insertR(link& h, Item x)
        { if (h == 0) { h = new node(x); return; }
          if (x.key() < h->item.key()) 
               insertR(h->l, x);
          else insertR(h->r, x);
        }
	  int heightR( link h )
	  {  if( h == 0 ) return -1;
	  else return max( heightR( h->l ), heightR( h->r )) + 1;
	  }
    public:
      ST(int maxN)
        { head = 0; }
      Item search(Key v) 
        { return searchR(head, v); } 
      void insert(Item x)
        { insertR(head, x); }
	  int height()
	  { return heightR( head ); }
  };


// Stokkunarfall til að rugla stökunum
template <class Item>
void stokka( Item a[], int N )
{
	for( int i=N-1; i>0; i-- ) {
		int r = (32876*rand() + rand() ) % (i+1);
		exch( a[i], a[r] );
	}
}


// Prófunarforrit til að bera saman hraða mism. útfærsla
int main()
{
    int i;
    int N;

	cout << "Fjoldi staka: ";
	cin >> N;

    int *a = new int[N];			// Fylki fyrir inntaks gildi
    PQ<int> fb(N);					// Hrúga


	// Upphafsstilla slemibitölugjafa
	srand( (unsigned)time( NULL ) );

    // Búa til inntaksgildi...
    for( i=0; i<N; i++ )
        a[i] = (32768*rand() + rand()) % N;

	cout << "Setjum inn "<< N << " stok..." << endl;

    // Setja inn N stök...
    for( i=0; i<N; i++ )
        fb.insert( a[i] );

	// Í röð eftir hrúgufylki...
	ST<Item, int> t1(N);

	for( i=1; i<=N; i++ )
		t1.insert( Item(fb.get(i),1.0) );

	cout << "I rod, haed: " << t1.height() << endl;

	// Í öfugri röð eftir hrúgufylki...
	ST<Item, int> t2(N);

	for( i=N; i>0; i-- )
		t2.insert( Item(fb.get(i),1.0) );

	cout << "I ofugri rod, haed: " << t2.height() << endl;

	// Stokka fyrst...
	ST<Item, int> t3(N);

	for( i=0; i<N; i++ )
		a[i] = fb.get(i);
	stokka( a, N );

	for( i=N; i>0; i-- )
		t3.insert( Item(a[i],1.0) );

	cout << "Eftir stokkun, haed: " << t3.height() << endl;


	cout << "Laegsta hugsanlega haed er " << (int)(log(N)/log(2.0)) << endl;

    return 0;
}