priority_queue
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering condition.
This context is similar to a heap where only the max heap element can be retrieved (the one at the top in the priority queue) and elements can be inserted indefinitely.
Priority queues are implemented as container adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are popped from the "back" of the specific container, which is known as the top of the priority queue.
The underlying container may be any of the standard container class templates or some other specifically designed container class. The only requirement is that it must be accessible through random access iterators and it must support the following operations:
front()
push_back()
pop_back()
Therefore, the standard container class templates vector and deque can be used. By default, if no container class is specified for a particular priority_queue class, the standard container class template vector is used.
Support for random access iterators is required to keep a heap structure internally at all times. This is done automatically by the container adaptor by calling the algorithms make_heap, push_heap and pop_heap when appropriate.
In their implementation in the C++ Standard Template Library, priority queues take three template parameters:
1
2
template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
Where the template parameters have the following meanings:
T: Type of the elements.
Container: Type of the underlying container object used to store and access the elements.
Compare: Comparison class: A class such that the expression comp(a,b), where comp is an object of this class and a and b are elements of the container, returns true if a is to be placed earlier than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function. This defaults to less<T>, which returns the same as applying the less-than operator (a<b).
The priority_queue object uses this expression when an element is inserted or removed from it (using push orpop, respectively) to grant that the element popped is always the greatest in the priority queue.
In the reference for the priority_queue member functions, these same names (T, Container and Compare) are assumed for the template parameters.
Member functions
(constructor)
Construct priority queue (public member function )
empty
Test whether container is empty (public member function)
size
Return size (public member function)
top
Access top element (public member function)
push
Insert element (public member function)
pop
Remove top element (public member function)
priority_queue <Elem> c
創建一個空的queue 。
注：priority_queue構造函數有7個版本，請查閱MSDN
c.top()
返回隊列頭部數據
c.push(elem)
在隊列尾部增加elem數據
c.pop()
隊列頭部數據出隊
c.empty()
判斷隊列是否為空
c.size()
返回隊列中數據的個數
優先隊列容器也是一種從一端入隊，另一端出對的隊列。不同於一般隊列的是，隊列中最大的元素總是位於隊首位置，因此，元素的出對並非按照先進先出的要求，將最先入隊的元素出對，而是將當前隊列中的最大元素出對。 C++ STL 優先隊列的泛化，底層默認采用 vector 向量容器，使得隊列容器的元素可做數組操作，從而應用堆算法找出當前隊列最大元素，並將它調整到隊首位置，確保最大元素出隊。堆算法(heap algorithm) 具有 nLog(n) 階的算法時間復雜度，此外，優先隊列也可看作容器適配器，將底層的序列容器 vector 轉換為優先隊列priority_queue.
priority_queue 優先隊列容器的 C++ 標准頭文件也是 queue ，需要用宏語句 "#include <queue>" 包含進來。
同樣是因為僅需取隊首和隊尾元素的操作，因此 priority_queue 優先隊列容器也不提供迭代器，對其他任意位置處的元素進行直接訪問操作。使用時，一般用 priority_queue<T> 的形式進行具現， T 是優先隊列元素的一個具現類型。
創建 priority_queue 對象
使用 priority_queue 隊列之前，要先利用構造函數生成一個優先對象，才可進行元素的入隊、出對、取隊首及隊尾等操作。
1. priority_queue()
默認的構造函數，創建一個空的 priority_queue 對象。例如，下面一行代碼使用默認的 vector 為底層容器，創建了一個空的優先隊列對象 pq ，數據元素為 int 類型。
priority_queue<int> pq;
2. priority_queue(const priority_queue&)
復制構造函數，用一個優先隊列對象創建新的優先隊列對象。例如，下面一行代碼利用 priority_queue 對象 pq1 ，創建一個以雙向鏈表為底層容器的 priority_queue 對象 pq2 。
// priority_queue<int, list<int> > pq1;
priority_queue<int, list<int> > pq2(pq1);
元素入隊
優先隊列容器的元素入隊函數也是 push 函數，它調用堆算法函數將入隊的元素移至隊列堆中的正確位置，保證隊列優先級高的元素始終位於隊首。優先隊列也不預設固定的大小，因此 push 函數不判斷隊列空間是否已滿，都將元素放入隊列。push 函數不會返回元素入隊是否成功的信息。
void push(const value_type& x)
元素出對
優先隊列容器的元素出對函數為 pop 函數，將優先級最高的元素刪掉。該函數不判斷隊列是否已為空，都試圖將隊首元素刪除。一般要先判斷隊列不為空，才進行元素出對操作。
取隊首元素
優先隊列容器的 top 函數，可用來讀取隊首元素，即優先級最高的元素。這個函數實際是調用了底層容器的 front 函數。需要注意的是，優先隊列容器並不提供獲取隊尾元素的函數。如下是 top 函數的使用原型。
const value_type& top() const
隊列非空判斷
優先隊列的操作基本都要使用 empty 函數，判斷入隊和出對的優先隊列是否為空，再作下一步的操作。如下是 empty 函數的使用原型。
bool empty()
[cpp]
#include <iostream>
#include <queue>
using namespace std;
void test_empty()
{
priority_queue<int> mypq;
int sum (0);
for (int i=1;i<=100;i++) mypq.push(i);
while (!mypq.empty())
{
sum += mypq.top();
mypq.pop();
}
cout << "total: " << sum << endl;
}//total: 5050
void test_pop()
{
priority_queue<int> mypq;
mypq.push(30);
mypq.push(100);
mypq.push(25);
mypq.push(40);
cout << "Popping out elements...";
while (!mypq.empty())
{
cout << " " << mypq.top();
mypq.pop();
}
cout << endl;
}//Popping out elements... 100 40 30 25
void test_top()
{
priority_queue<string> mypq;
mypq.push("how");
mypq.push("are");
mypq.push("you");
cout << "mypq.top() is now:--->>> " << mypq.top() << endl;
}//mypq.top() is now:--->>> you
int main()
{
test_empty();
cout<<"\n***********************************************\n";
test_pop();
cout<<"\n***********************************************\n";
test_top();
cout<<"\n***********************************************\n";
priority_queue<float> q;
// insert three elements into the priority queue
q.push(66.6);
q.push(22.2);
q.push(44.4);
// read and print two elements
cout << q.top() << ' ';
q.pop();
cout << q.top() << endl;
q.pop();
// insert three more elements
q.push(11.1);
q.push(55.5);
q.push(33.3);
// skip one element
q.pop();
// pop and print remaining elements
while (!q.empty())
{
cout << q.top() << ' ';
q.pop();
}
cout << endl;
}
/******************
運行結果:
total: 5050
***********************************************
Popping out elements... 100 40 30 25
***********************************************
mypq.top() is now:--->>> you
***********************************************
66.6 44.4
33.3 22.2 11.1
Process returned 0 (0x0) execution time : 0.055 s
Press any key to continue.
********************/
#include <iostream>
#include <queue>
using namespace std;
void test_empty()
{
priority_queue<int> mypq;
int sum (0);
for (int i=1;i<=100;i++) mypq.push(i);
while (!mypq.empty())
{
sum += mypq.top();
mypq.pop();
}
cout << "total: " << sum << endl;
}//total: 5050
void test_pop()
{
priority_queue<int> mypq;
mypq.push(30);
mypq.push(100);
mypq.push(25);
mypq.push(40);
cout << "Popping out elements...";
while (!mypq.empty())
{
cout << " " << mypq.top();
mypq.pop();
}
cout << endl;
}//Popping out elements... 100 40 30 25
void test_top()
{
priority_queue<string> mypq;
mypq.push("how");
mypq.push("are");
mypq.push("you");
cout << "mypq.top() is now:--->>> " << mypq.top() << endl;
}//mypq.top() is now:--->>> you
int main()
{
test_empty();
cout<<"\n***********************************************\n";
test_pop();
cout<<"\n***********************************************\n";
test_top();
cout<<"\n***********************************************\n";
priority_queue<float> q;
// insert three elements into the priority queue
q.push(66.6);
q.push(22.2);
q.push(44.4);
// read and print two elements
cout << q.top() << ' ';
q.pop();
cout << q.top() << endl;
q.pop();
// insert three more elements
q.push(11.1);
q.push(55.5);
q.push(33.3);
// skip one element
q.pop();
// pop and print remaining elements
while (!q.empty())
{
cout << q.top() << ' ';
q.pop();
}
cout << endl;
}
/******************
運行結果:
total: 5050
***********************************************
Popping out elements... 100 40 30 25
***********************************************
mypq.top() is now:--->>> you
***********************************************
66.6 44.4
33.3 22.2 11.1
Process returned 0 (0x0) execution time : 0.055 s
Press any key to continue.
********************/
