priority queue.cpp

算法中的优先队列的实现

#include<iostream>
using namespace std;
typedef int queue_entry;
#define max 20            // small number for test

class Priority_queue{
public:
    Priority_queue()           // constructor
        { count=0; }
    void push(const queue_entry &item); 
    void pop();                       // remove the largest key;
    const queue_entry& top();  // return the largest key

    int  size ()
        {    return count;    }         // return the number of the elements;
    bool empty() 
       {    return count==0; }        // test if the queue is empty;

protected:
    void max_heapify(int i);        // 维护最大堆性质
    queue_entry entry[max];     //元素数组
    int count;
};

const queue_entry&  Priority_queue::top(){
    if(count>0)
        return entry[0];
    else
        exit(1);
}   

void Priority_queue::max_heapify(int i) {
    int largest, left, right;
    bool flag;
    do{
        flag=0;
        left = 2 * i + 1; 
        right= left + 1;
        if(left < count && entry[left]>entry[i]) 
        {
            largest=left;
            flag=1;
        }
        else largest=i;
        if(right < count && entry[right]>entry[largest])
        {        
            largest=right;
            flag=1;
        }
        if(flag) 
            swap(entry[i], entry[largest]);
        i = largest;
    }    while(flag);
    return;
}


void Priority_queue::push(const queue_entry &item){
    entry[count]=item;
    int i=count;
    count++;
    int parent=(i-1)/2;
    while(i > 0 && entry[parent] < entry [i] )     
      {
        swap (entry[i], entry[(i-1)/2]);
        i = parent;
        parent = (i-1)/2;
    }
    return;
}

void Priority_queue::pop(){
    if(count>0)
    {
        entry[0] = entry[count-1];
        count--;
        max_heapify(0);
    }
    else
        exit(1);
    return;
}

// test the Priority_queue
int main(){
    Priority_queue q1;

   q1.push( 10 );
   q1.push( 35 );
   q1.push( 35 );
   q1.push( 30 );
   q1.push( 25 ); 
   q1.push( 35 );
   int len;
   len= q1.size( );
   cout << "The Priority_queue length is " << len<< "." << endl;

   const int& i1 = q1.top( );
   cout << "The element at the top of the Priority_queue is "
        << i1<< "." << endl;

   q1.pop( );

   int i2 = q1.size( );
   cout << "After a pop, the Priority_queue length is " 
        << i2 << ".";

   const int& i3 = q1.top( );
   cout << "And the element at the top of the priority_queue is " 
        << i3<< "." << endl;
   system("pause");
   return 0;
}