Thread: Priority Heaps

You will be writing heap code where the heap priority is no longer decided by a
simple key value. Instead the key value of a node will be an index into an array of
pointers to data structures, and one field from within the structures will be used for
prioritising. The priority will be how close a given town is to Dublin; the closer the
town, the hight the priority is.
Place all your code in 1 file called TownHeap.cpp. It should include
• class and struct declarations
• class method implementations
• a main() function for running the program and testing the heap code.

Thats the question that i have been given and the following code is my attempts to get it working so far. If you have any questions about the code and ill post up answers as soon as i can.

The Class, the struct and the display function seem to be working, if you could make comments as to how i would get the rest of the functions working it would be a great help.

DAVE.

Code:

// TownHeap.cpp


#include <iostream.h>
#include <limits.h>
#include <math.h>

#define maxH 100


struct Town
{
   char * name;
   int dist;
   long pop;

   Town( char* n, int d, long p)
   {
      name = n; dist = d; pop = p;
   }
};


class TownHeap
{

	private:
   		Town ** town;
   		int *h;
   		int N;
   		void siftUp( int k);
   		void siftDown( int k);

	public:
   		TownHeap( Town * t[]);

   		void insert( int x);
   		int remove();

   		void display();
};


// put the TownHeap methods in here

void TownHeap::siftUp(int k)
{



   /*int v ;
   v = town[h[k]];
   while( town[h[k/2]] >= v )
   {
   	h[k] = h[k/2];
      k = k/2 ;
   }
   h[k] = v ;


	/*h[0] = 0;
   town[0]->dist = INT_MIN;

   int index = h[k];

   dist = town[k] -> dist;

   while( dist < town [h[k/2]] -> dist)
   {
   	h[k] = h[k/2];
      k = k/2;
   }

   h[k] = index;
   */
}

void TownHeap::siftDown(int k)
{

   int j; int v;
   v = town[h[k]]->dist ;
   while (k <= N/2)
   	{
      	j = k+k ;
         if(j<N && (town[h[j]]->dist)>(town[h[j+1]]->dist)) j++;
         if(v >= town[h[j]]->dist) break ;
         h[k] = h[j]; k = j ;
      }
      town[h[k]]->dist = v ;

	/*int index, index2;

   index = h[k];

   while( k <= N/2)
   {
      index2 = 2 * k;

      if ( index2 < N && h[index2] < h[index2+1])
      {
      	++index2;
      }

      if ( index >= h[index])
      {
      	break;
      }

      h[k] = h[index2];
      k = index2;
   }

   h[k] = index;*/
}

void TownHeap::insert(int x)
{
   h[++N] = x;
   siftUp(N);
}

int TownHeap::remove()
{
   h[0] = h[1];
   h[1] = h[N--];
   siftDown(1);
   return h[0];
}



void TownHeap::display()
{
	for( int i = 1 ; i < 10 ; ++i)
	{
		cout << town[i]->name << ' ' << town[i]->dist << ' ' << town[i]->pop << endl;
	}
}


TownHeap::TownHeap( Town * t[])
{
   town = t;
   N = 0;
   h = new int[maxH+1];
}



// main function for testing code
void main()
{
	Town * town[30];
	TownHeap h(town);   // calls the TownHeap() constructor

   town[0] = new Town("", 0, 0L);
   town[1] = new Town("A", 5, 15000L);
   town[2] = new Town("B", 10, 15000L);
   town[3] = new Town("C", 15, 15000L);
   town[4] = new Town("D", 20, 15000L);
   town[5] = new Town("E", 25, 15000L);
   town[6] = new Town("F", 30, 15000L);
   town[7] = new Town("G", 35, 15000L);
   town[8] = new Town("H", 40, 15000L);
   town[9] = new Town("I", 45, 15000L);
   town[10] = new Town("J", 50, 15000L);
   town[11] = new Town("K", 55, 15000L);
   town[12] = new Town("L", 60, 15000L);


   h.display();
   h.remove();
   h.display();


}

I highly recommend not having a struct Town and a variable town. The TownHeap uses a variable called town and so does the main function; hard to tell what's what. I may be mistaken, but it doesn't seem that the TownHeap connects each town to the next, do they need to be connected for moving/sifting? Please state which functions don't work and what they are supposed to do.

Originally Posted by neandrake

I highly recommend not having a struct Town and a variable town. The TownHeap uses a variable called town and so does the main function; hard to tell what's what. I may be mistaken, but it doesn't seem that the TownHeap connects each town to the next, do they need to be connected for moving/sifting? Please state which functions don't work and what they are supposed to do.

The siftUp Function does not work at the moment. Its Function is to sift upwards through the heap until it finds a higher value than its current arguement. The insert function calls to the siftUp function to enable it to insert the new town into the correct position on the heap.

So if we could consentrate on inserting a new town into the heap it would be a great step forward for us.

Again if you have any questions i will answer as soon as i can.

Thanks,

DAVE.