Priority_queue and imitation functions
But it can be clearly said that although he is called the priority queue, it does not meet the characteristics of the queue.
- Priority queue is a container adapter, according to strict weak sorting standards, its first element is always the largest of the elements it contains.
- This context is similar to the heap, which can be inserted at any time in the heap, and the maximum pile elements can be retrieved (the element in the top in the priority queue).
The
- Priority queue is implemented as a container adapter. The container adapter is to be encapsulated as a bottom container class. Queue provides a set of specific member functions to access its elements. The element pops up from the “tail” of a specific container, which is called the top of the priority queue.
- The bottom container can be any standard container template or other specific design containers. The container should be able to access the iterator through random access and support the following operations:
- Empty (): Detecting whether the container is empty
- SIZE (): The number of effective elements in the return container
- Front (): Reference to the first element in the container
- push_back (): Insert elements at the end of the container
- pop_back (): Delete the tail element of the container
- Standard container class Vector and Deque meet these needs. by default,If you do not instantly use the specified container class for a specific Priority_queue class, use Vector
twenty one# . (Deque’s random access data is still relatively troublesome)
- You need to support random access to the iterators so that you can always maintain the heap structure internally. The container adapter automatically calls the algorithm function make_heap, push_heap, and POP_HEAP by the time to complete the operation.
Priority queue uses Vector as a container for its underlying storage data. On the vector, the pile algorithm is used to construct the element in Vector into a structure. Therefore Use Priority_queue.Note: Priority_queue is a large pile by default。
#pragma once
#include<assert.h>
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)const
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)const
{
return x > y;
}
};
namespace wzy
{
// By default, the priority queue is a large pile
// This defines us by ourselves, but in the standard library, a lot of less is passed, and the small pile is a Greater
template<class T, class Container = vector<T>,class Compare = Greater<T>>
class priority_queue
{
public:
//priority_queue()
//{}
// As long as you write a constructor, then the compiler will not generate the rest in the default, so you must make up for it yourself
// but this complemented constructor is not nothing. For the custom type that we define, he will automatically call the constructor initialization at the beginning
priority_queue() = default; // C ++ 11 Keywords forced the compiler to generate a default constructor for you
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first,last)
{
// Start with the first non -leaf node adjustment
// Construction from bottom to top
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(i);
}
// Construction from top to bottom
//for (int i = 1; i < _con.size(); ++i)
//{
// AdjustUp(i);
//}
}
// Because in the class at this time, you can access its member variables by default, so only one parameter needs to be passed
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0) // Due to the calculation formula above, when your child is 0, Parent is 0, and it has been terminated
// In rude and simple understanding: When your Child node is 1, the Parent node is just 0. At this time, there is a parent node, but once your child node is less than 1,
// Directly, Parent can't find it.
{
//if (_con[child] > _con[parent])
if (com(_con[child] , _con[parent]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
// The pile at this time will not be satisfied with a lot of interest, so you need to adjust it up to maintain the characteristics of a large pile. The child's node is smaller than the father's node.
AdjustUp(_con.size() - 1);
}
void AdjustDown(int parent)
{
Compare com;
size_t child = parent * 2 + 1;
// There is a left child, the right child may not exist
while (child < _con.size())
{
// First find out which one of the larger children is
// If you do not add child+1 <_on.size (), then you will find that the following _Con [Child+1] is a [], which is an assertion.
//if (child + 1 < _con.size() && _con[child + 1] > _con[child])
if (child + 1 < _con.size() && com(_con[child + 1] , _con[child]))
{
++child;
}
// Then compare from the larger child and father node
//if (_con[child] > _con[parent])
if (com(_con[child] , _con[parent]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
assert(size() > 0);
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
const T& top()const
{
return _con[0];
}
size_t size()const
{
return _con.size();
}
bool empty()const
{
return _con.empty();
}
private:
Container _con;
};
}
4 4 is a class. In this class, the operator () is re -loaded, so the objects that this class instance can be used like a function!
The reason why
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)const
{
return x < y;
}
};
int main()
{
Less<int> less;
less(1, 2);
}
uses the imitation function is because for the construction of a large pile, the two interfaces of Adjustup () and Adjustdown () are only a symbol of greater than or less than less. After writing a large pile of Copy, modify a symbol to generate small piles, so it will cause the length of the code.