Priority Heaps

This is a discussion on Priority Heaps within the C++ Programming forums, part of the General Programming Boards category; You will be writing heap code where the heap priority is no longer decided by a simple key value. Instead ...

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    44

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

  2. #2
    30 Helens Agree neandrake's Avatar
    Join Date
    Jan 2002
    Posts
    640
    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.
    Environment: OS X, GCC / G++
    Codes: Java, C#, C/C++
    AOL IM: neandrake, Email: neandrake (at) gmail (dot) com

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    44
    Quote 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.
    Dangerous Dave

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. priority inversion due to pthread_mutex_lock(): how to avoid?
    By mynickmynick in forum C Programming
    Replies: 11
    Last Post: 04-07-2009, 10:34 AM
  2. crazy pipe/fork
    By fortune2k in forum C Programming
    Replies: 8
    Last Post: 03-13-2009, 11:28 AM
  3. Priority queue
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 12-03-2007, 12:30 AM
  4. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-14-2007, 11:48 PM
  5. priority list won't work, i give up
    By teamster in forum C Programming
    Replies: 8
    Last Post: 10-19-2006, 12:26 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21