<Introduction to algorithms> chapter 6.5
(《算法导论.第6章 优先级队列) ,,
函数名参照C++ STL中priority_queue

数组实现.源代码:

#include<iostream> 
using namespace std; 
 
typedef int queue_entry; 
#define maxque 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[maxque];   //  元素数组 
    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 ); 
 
   int i; 
   i = q1.size( ); 
   cout << "The Priority_queue length is " << i << "." << endl; 
 
   const int& ii = q1.top( ); 
   cout << "The element at the top of the Priority_queue is " 
        << ii << "." << endl; 
 
   q1.pop( ); 
 
   int iii = q1.size( ); 
   cout << "After a pop, the Priority_queue length is " 
        << iii << "." << endl; 
 
   const int& iv = q1.top( ); 
   cout << "After a pop, the element at the top of the " 
        << "priority_queue is " << iv << "." << endl; 
 
   return 0; 
}