For my C++ Data Structure class, we are implementing a dial-up modem simulator. Our professor gave us a working source file that uses the STL priority queue, but our job is to replace that by implementing a binary heap. I went in to go see her for help today with what exactly binary heap is, but she basically told me and my friend to transfer to IT :(. She just started talking about it on Monday, both priority-queues and binary heap, which she rushed through in an hour, she started talking about a new subject today because her slides aren't done so she's going to resume with binary heap on Friday which is when the program is due.

I understand this much, binary heap is the back-end of priority queue. But do I sort when the elements are being inserted or being popped? And she mentioned using a vector or a list, where does that come in play when you're just building a tree? Also I don't understand why this code works on her's:

typedef priority_queue<Event,vector<Event>,greater<Event> > PQ;

Is that just how you declare a STL priority queue? The program is hard to describe so I will paste it at the bottom. It's only one source file.

Note: Random.h just has functions that return random numbers according to some stats distribution.

modemSimu.cpp:

#include <queue>
#include <vector>
#include <functional>  // for greater()
#include <climits>     // for INT_MAX
#include <iostream>
#include "random.h"
using namespace std;

class Event{
    enum { DIAL_IN = 1, HANGUP = 2 };
  public:
    Event( int name = 0, int tm = 0, int type = DIAL_IN )
         : time( tm ), who( name ), what( type ) { }
    bool operator> ( const Event & rhs ) const
      { return time > rhs.time; }
    friend class ModemSim;
  private:
    int who;        // the number of the user
    int time;       // when the event will occur
    int what;       // DIAL_IN or HANGUP
};

typedef priority_queue<Event,vector<Event>,greater<Event> > PQ; 

class ModemSim{
  public:
    ModemSim( int modems, double avgLen, int callIntrvl );
      // Add a call to eventSet at the current time,
      // and schedule one for delta in the future.
    void nextCall( int delta );

      // Run the simulation
    void runSim( int stoppingTime = INT_MAX );

  private:
    Random r;                       // A random source
    PQ eventSet;                    // Pending events

      // Basic parameters of the simulation
    int freeModems;                 // Number of modems unused
    const double avgCallLen;        // Length of a call
    const int freqOfCalls;          // Interval between calls
};

// Constructor for ModemSim.
ModemSim::ModemSim( int modems, double avgLen, int callIntrvl )
  : freeModems( modems ), avgCallLen( avgLen ),
    freqOfCalls( callIntrvl ), r( (int) time( 0 ) )
{
    nextCall( freqOfCalls );  // Schedule first call
}

// Place a new DIAL_IN event into the event queue.
// Then advance the time when next DIAL_IN event will occur.
// In practice, we would use a random number to set the time.
    void ModemSim::nextCall( int delta ){
    static int nextCallTime = 0;
    static int userNum = 0;

    eventSet.push( Event( userNum++, nextCallTime ) );
    nextCallTime += delta;
}

// Run the simulation until stopping time occurs.
void ModemSim::runSim( int stoppingTime ){
    static Event e;
    int howLong;

    while( !eventSet.empty( ) ){
        e = eventSet.top( );
        eventSet.pop( );
        if( e.time > stoppingTime )
            break;

        if( e.what == Event::HANGUP )    // HANGUP
        {
            freeModems++;
            cout << "User " << e.who << " hangs up at time "
                 << e.time << endl;
        }
        else                             // DIAL_IN
        {
            cout << "User " << e.who << " dials in at time "
                 << e.time << " ";
            if( freeModems > 0 )
            {
                freeModems--;
                howLong = r.negExp( avgCallLen );
                cout << "and connects for "
                     << howLong << " minutes" << endl;
                e.time += howLong;
                e.what = Event::HANGUP;
                eventSet.push( e );      // insert HANGUP
            }
            else
                cout << "but gets busy signal" << endl;
            nextCall( freqOfCalls );
        }
    }
}


// Simple main to test ModemSim class.
int main( )
{
    int numModems;
    int totalTime;
    double avgConnectTime;
    int dialInFrequency;

    cout << "Enter number of modems, length of simulation,\n"
         << " average connect time, how often calls occur: ";

    cin >> numModems >> totalTime >>
                    avgConnectTime >> dialInFrequency;

    ModemSim s( numModems, avgConnectTime, dialInFrequency );
    s.runSim( totalTime );

    return 0;
}

• c++
• data-structures
• priority-queue
• binary-heap

Do you not have a text? If not, I suggest you look up heap sort in virtually any data structures text, e.g. Aho, Hopcroft and Ullman. Heaps are a sort of binary tree that is normally stored in an array (vector) where the left half of the tree is in the bottom half of the array and the right half in the top half of the array (recursively). You only need the index into the array to determine the location in the tree (and vice versa). A heap is not actually maintained sorted; the element at the front is always the min (or it could be max); and there is an operation normally called re-heapify that takes log n time to restore the heap property after an element is added or removed. Removal is only from the front. That should give you an idea of how heaps and priority queues and vectors are related. The algorithm for re-heapify should be in your text.