1. Introduction to priority queues
A priority queue is a special queue data structure. It is a queue, but it is not exactly because it prioritizes the loaded data and finds an element with the largest or least priority. The next element that comes out of the queue is this element, so it is not completely a queue. The priority queue is widely used in the fields of task scheduling, resource allocation, event processing, Dijkstra algorithm, A* search algorithm and other fields.
2. Design of priority queues
Personally, designing a priority queue is a process of heap establishment and adjustment. Because elements are to be loaded, we use vector as member variables, and the subsequent management of the vector variable is enough. Because we simply design a priority queue, we do not design a process of comparing functions in the priority queue for comparison, but just a simple process of comparing sizes. First of all, we need to design upward adjustment functions and downward adjustment functions, because the constructor and destructor are very simple, so I will not elaborate on it here.
Adjust the function upward
The upward adjustment function is to compare the child node with the parent node. Here we assume that we build a small heap. If the child node is smaller than the parent node, then there is a problem with this heap. Therefore, we need to exchange and exchange the child node with the parent node. However, we need to consider whether the child node, that is, the current parent node, has a wrong relationship with its current parent node after exchange. Therefore, we need to loop. Only when the node is 0, that is, the root node or the child node is smaller than the parent node, loop exit
void siftUp(size_t index)
{
while (index > 0)
{
int father = index / 2;
if (list[father] > list[index])
{
swap(list[father], list[index]);
index = father;
}
else
{
break;
}
}
}Adjust the function downward
Down adjustment is to judge whether you are younger than both your children. The logic is similar to the upward adjustment function, but you have to compare with both children once, or find the youngest child. The main thing is to know that the child is index/2-1 and index/2-2.
void siftDown(size_t index)
{
while (index <= ())
{
leftson = index * 2 + 1;
rightson = index * 2 + 2;
if (list[index] > list[leftson])
{
swap(list[index], list[leftson])
index = leftson;
}
else if (list[index] > list[rightson])
{
swap(list[index], list[rightson]);
index = rightson;
}
else
{
break;
}
}
}Build heap functions
The first step in the constructor is to copy the corresponding vector, and the vector obtained is likely not a heap, so it needs to be adjusted so that it can become a heap that complies with the rules. Generally, there are two strategies for building a heap, one is the bottom-up sift down method, and the other is the top-down sift up method. Here we use the method of sit down adjustment down to find the last non-leaf node, that is, ()/2, and then adjust each non-leaf node downward.
explicit Heap(const std::vector<T>& array)
:list(array)
{
buildHeap();
}
void buildHeap()
{
for (int i = () / 2 ; i >=0 ; i--)
{
siftDown(i);
}
}Insert function
When we insert an element, we first insert the vector list at the end, and then adjust the element upward, making the heap regular
void insert(const T& value)
{
(value);
siftUp(() - 1);
}Get top element function
We build this heap or maintain this priority queue to get a valuable element. Of course, the most valuable elements in this heap are pile top elements, but when we get the heap top element, the heap will also be destroyed. Therefore, we usually exchange the heap top element with the last element, and then adjust the heap top element downward to keep the heap top element in the right rules.
void removeTop()
{
if (()) {
throw std::out_of_range("Heap is empty");
}
swap(list[0], list[() - 1]);
siftDown(0);
(() - 1);
}This is the end of this article about using C++ to build a priority queue. For more related C++ priority queue content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!