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
class Compare = less
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
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
创建一个空的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
同样是因为仅需取队