ヒープソートと優先度キューとは何ですか？

Question

私のC++データ構造クラスでは、ダイヤルアップモデムシミュレータを実装しています。私たちの教授は、STL優先順位キューを使用する作業ソースファイルを私たちに与えましたが、私たちの仕事は、バイナリヒープを実装することでそれを置き換えることです。私は今、バイナリヒープとは何かを助けてくれるように彼女に会いに行きましたが、彼女は基本的に私と私の友人にITに移籍するように言いました:(彼女は月曜日、優先順位キューとバイナリヒープ彼女は1時間後に突入しました。彼女はスライドが終了していないので、今週の新しい科目について話を始めました。

私はこれを多く理解しています。バイナリヒープはバイナリヒープで再開する予定です。ヒープは優先順位キューのバックエンドですが、要素が挿入されたりポップされたりするとソートされますか？また、ベクトルやリストを使用して説明しました。私はなぜこのコードが彼女の作品であるのかわかりません：

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

STL優先度キューを宣言するだけですか？プログラムは記述が難しいので、私はそれを最下部に貼り付けます。それは唯一のソースファイルです。

注：Random.hには、いくつかの統計分布に従って乱数を返す関数があります。

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

Answer 1

テキストを持っていないのですか？もしそうでなければ、事実上どんなデータ構造のテキストでもヒープソートを調べることをお勧めします。アホ、ホプクロフト、ウルマン。ヒープは、ツリーの左半分が配列の下半分にあり、右半分が配列の上半分にある（再帰的に）配列（ベクトル）に格納される一種のバイナリツリーです。ツリー内の位置を決定するためには、配列へのインデックスのみが必要です（逆もまた同様です）。ヒープは実際にはソートされません。正面の要素は常に最小値です（または最大値にすることもできます）。要素が追加または削除された後にヒーププロパティを復元するためにログn時間がかかるre-heapifyと呼ばれる操作があります。取り外しは前面からのみです。これは、ヒープと優先順位のキューとベクトルがどのように関連しているかのアイデアを与えるはずです。再heapifyのアルゴリズムはあなたのテキストにあるはずです。