The underlying structure of priority_queue
We have already studied stacks and queues, and they are all adapted from a container. The prority_queue we are going to learn today is also a container adapter. In the usage section of priority_queue, we already know that if we want to adapt priority_queue, the underlying container must have the following interface:
- 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 elements at the end of the container.
Adapter is a design pattern (a design pattern is a set of code design experiences that are repeatedly used, known to most people, classified and cataloged). This pattern converts the interface of a class into another one that the customer wants. interface.
When learning C language, we have already learned about the data structure of heap. At that time, we used arrays as the underlying data structure of the heap. Therefore, when we simulated the implementation of priority_queue, we would use vector serves as the underlying data structure of priority_queue. Of course, there is no problem with deque, but it is not as efficient as vector. Because we will use operator[] extensively, in comparison we will tend to choose vector to simulate the implementation of priority_queue.
Basic structure implementation of priority_queue
The general idea of implementing priority_queue is similar to the simulated implementation of stack and queue. priority_queue involves more algorithms and detailed processing.
#pragma once
namespace Tchey
{<!-- -->
template<class T, class Container = vector<T>>
class priority_queue
{<!-- -->
public:
private:
Container_con;
};
}
But the template class of priority_queue we defined in this way seems wrong! Because the priority_queue in the library needs to pass three template parameters when you want to build a small heap: stores a small heap of type int: priority_queue. What is this greater?
This greater is a template class priority_queue that is the key to instantiating large and small heaps!
Functions
Looking at its structure, greater should also be a template class. In this class, the parentheses operator is overloaded, namely: operator(), so that an object of the class can be called like a function. This stuff is called functor. Let’s look at a simple example:
struct GetLessNum
{<!-- -->
int operator()(const int & amp; a, const int & amp; b)
{<!-- -->
return a < b ? a : b;
}
};
int main()
{<!-- -->
GetLessNum getLessNum;
int a = 10, b = 5;
cout << getLessNum(a, b) << endl; //Output: 5
return 0;
}
In the above example, we defined a GetLessNum class, which overloaded the parentheses operator. In the main function, an object is instantiated, and operator() is called through the object to achieve the effect of function calling through the class object. This is a functor!
Secret greater
Similarly, in the greater template class, the parentheses operator is also overloaded. When we built the big pile, the last two template parameters were not passed in, so it can be seen that default values were given. In the C language stage, we have already learned about heaps and know the difference between building a large heap and a small heap: only the comparison logic in the upward adjustment algorithm and the downward adjustment algorithm is different, the rest are the same.
Basic C language data structure (11)—-Heap_Ji Ruyi’s blog-CSDN blog
So we can use template parameters to control the comparison logic implemented by the two algorithms in priority_queue! In this way, different heaps can be built based on the different template parameters passed in!
namespace Tchey
{<!-- -->
template<class T>
struct less
{<!-- -->
bool operator()(const T & amp; e1, const T & amp; e2)
{<!-- -->
return e1 < e2;
}
};
template<class T>
struct greater
{<!-- -->
bool operator()(const T & amp; e1, const T & amp; e2)
{<!-- -->
return e1 > e2;
}
};
}
When using the push function of priority_queue, the upward adjustment algorithm will be used: for a large heap, if the value of the child node is greater than the value of the parent node, then the two need to be exchanged. The value of a node, for a small heap; if the value of the child node is less than the value of the parent node, then the values of the two nodes need to be exchanged.
So we can control it through the third template parameter passed in: If less is passed in, it happens that the opertor(( ) is the comparison logic of less than, which is the upward adjustment algorithm of the small heap; if greater is passed in, it happens to be the in is greater than comparison logic, which is a lot of upward adjustment algorithms.greater >opertor()
Through the control of template parameters, priority_queue can implement large and small heaps at the same time, without having to write large and small heaps separately.
The basic structure of priority_queue can be written like this:
namespace Tchey
{<!-- -->
template<class T>
struct less
{<!-- -->
bool operator()(const T & amp; e1, const T & amp; e2)
{<!-- -->
return e1 < e2;
}
};
template<class T>
struct greater
{<!-- -->
bool operator()(const T & amp; e1, const T & amp; e2)
{<!-- -->
return e1 > e2;
}
};
template<class T, class Container = vector<T>, class Cmp = Less<T>>
class priority_queue
{<!-- -->
public:
private:
Container_con;
};
}
Priority_queue function implementation
Upward adjustment algorithm
When we insert data into a heap, we will use the upward adjustment algorithm: Take a big heap as an example. If you insert a piece of data into the big heap, you will naturally need to adjust it so that the inserted data is re-aligned with the original big heap. Form a new big pile!
In this insertion example, we insert node 9, which we might as well name child. His parent node 6 may as well be named parent. child is greater than parent, exchange the values of the two nodes. Then update child and parent. At this time, child is still greater than parent and the values of the two nodes are exchanged. Update child and parent again. Found parent < 0, end the loop. Or child < parent also needs to end the loop during the comparison.
This is the upward adjustment algorithm for large heaps. As for small heaps, just reverse the logic.
If you want priority_queue to decide whether it is a large heap comparison logic or a small heap comparison logic based on the parameters passed in, you cannot hard-code the comparison logic here, but compare it based on the functor!
void AdjustUp(int child)
{<!-- -->
Cmp cmp; //Instantiate an object based on the class of the third template parameter
int parent = (child - 1) / 2; //Find parent based on child
while(child)
{<!-- -->
if(cmp(_con[parent], _con[child])) //Call operator() to compare
{<!-- -->
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else //Exit the loop directly if the conditions are not met
break;
}
}
Downward adjustment algorithm
The downward adjustment algorithm is used in the pop function! The logic of pop is to exchange the data at the top of the heap with the last data in the heap, and then adjust the algorithm downwards for the element with index 0 to meet the requirements of the heap!
Let’s look at the above example: this is a big heap, delete the element at the top of the heap: we first exchange the 7 at the top of the heap with the last data 0 in the heap. Then for the element with index 0, you might as well name it parent. The logic of downward adjustment is: select the larger of the left and right children of parent, name it child, and then compare it with parent. If child is greater than parent, exchange the parent and child nodes. . Otherwise, the logic of the downward adjustment algorithm ends. If the child is greater than or equal to the size of vector, the loop will also end.
The same upward adjustment algorithm, if it is a small heap, only the comparison logic is different, the other steps are the same! Therefore, the comparison of the downward adjustment algorithm between child and parent cannot use the greater than or less symbol to hard-code the comparison logic. Instead, use functors to implement comparison logic.
void AdjustDown(int parent)
{<!-- -->
Cmp cmp; //instantiate the functor object
int n = _con.size(); //size of vector
int child = parent * 2; //Find child through parent
while(child < n)
{<!-- -->
//Select the larger or smaller of the left and right children, depending on the value passed in the third template parameter
if(child + 1 < n & amp; & amp; cmp(_con[child], _con[child + 1]))
child + + ;
//If the conditions are met, exchange
if(cmp(_con[parent], _con[child]))
{<!-- -->
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2;
}
else //Exit directly if not satisfied
break;
}
}
void push(const T & amp; val)
When you finish writing the upward adjustment algorithm and the downward adjustment algorithm, the interface implementation of the heap will be at your fingertips! The push function inserts an element into the heap. We only need to push_back an element in vector and then use the upward adjustment algorithm. !
void push(const T & amp; val)
{<!-- -->
_con.push_back(val);
AdjustUp(_con.size() - 1);
}
void pop()
Deleting the element at the top of the heap only requires us to swap the element with index 0 in vector with the last element in vector, and then call pop_back() interface, and finally use the downward adjustment algorithm once on the element with index 0!
void pop()
{<!-- -->
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
bool empty()
We only need to return whether vector is empty!
void empty()
{<!-- -->
return _con.empty();
}
size_t size()
Similarly, we only need to return the size of the vector!
size_t size()
{<!-- -->
return _con.size();
}
T & amp; top()
Returning the element at the top of the heap is to return the element with index 0 in vector.
void top()
{<!-- -->
assert(_con.size());
return _con[0];
}
