什麼是堆排序和優先隊列？

Question

對於我的C++數據結構類，我們實現了一個撥號調制解調器模擬器。我們的教授給了我們一個使用STL優先級隊列的工作源文件，但我們的工作是通過實現一個二進制堆來替代它。我今天去看她求助二進制堆，但她基本上告訴我和我的朋友轉移到IT :(她星期一剛開始討論它，包括優先級隊列和二進制堆，她在一小時內衝了過來，她今天開始談論一個新的主題，因爲她的幻燈片沒有完成，所以她將在星期五恢復二元堆，這是程序到期時的情況。堆是優先級隊列的後端，但是當元素被插入或被彈出時，我會進行排序嗎？她提到使用向量或列表，當你剛剛構建樹時，它會在哪裏發揮作用？我不明白爲什麼這段代碼適用於她的：

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次以恢復堆屬性。去除只是從前面。這應該讓你知道堆和優先級隊列和向量是如何相關的。重新heapify算法應該在您的文本。