One 、priority_queue Introduction to

1. Priority queue is a kind of Container adapter , According to the strict weak sorting criteria , Its first element is always the largest of the elements it contains .
2. This context is similar to heap , You can insert elements into the heap at any time , And only the largest heap element can be retrieved ( The top element in the priority queue ).
3. The priority queue is implemented as a container adapter , The container adapter encapsulates a specific container class as its underlying container class ,queue Provide a specific set of member functions to access its elements . Element from a specific container “ The tail ” eject , It is called the top of the priority queue .
4. The underlying container can be any standard container class template , It can also be other specially designed container classes . Containers should be accessible through random access iterators , And supports the following operations ：

• empty()： Check whether the container is empty
• size()： Returns the number of valid elements in the container
• front()： Returns a reference to the first element in the container
• push_back()： Insert the element at the end of the container
• pop_back()： Delete the container tail element

5. Standard container class vector and deque Meet these needs . By default , If not for a specific priority_queue Class instantiation specifies the container class , Then use vector.
6. Need to support random access iterators , So that the heap structure is always maintained internally . The container adapter automatically calls algorithm functions when needed make_heap、push_heap and pop_heap To automatically complete this operation .
7. functor / Function object

Two 、priority_queue Use

Priority queues are used by default vector As its underlying container for storing data , stay vector The heap algorithm is used to vector A structure in which elements are constructed in piles , therefore priority_queue Is a pile of , All locations that need to use the heap , You can consider using priority_queue.
Be careful ： By default priority_queue It's a lot .

#include<iostream>
#include<queue>
#include<functional>//greater Algorithm header file 
using namespace std;
void test_priority_queue()
{
    
	//  The default is a lot of —— The default functor is less
	//priority_queue<int> pq;

	//  The priority of small control is high —— Give affine function greater
	//  Pass in the third template parameter , You must explicitly pass in the second 
	priority_queue<int,vector<int>,greater<int>> pq;
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);

	while (!pq.empty())
	{
    
		cout << pq.top() << " ";
		pq.pop();
	}
}
int main()
{
    
	test_priority_queue();
	return 0;
}

3、 ... and 、priority_quque Of OJ topic

No K A big element

The time complexity of the first two methods is ：O(nlogn)

After optimization ：O(n+klogn)

But when n When a large , And n Far greater than k, To build a k A few small piles
The following extreme solution ：O(nlogk)