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();
}
