Priority Queue — [Introduction to Algorithms]
About Heap
In a previous post, I introduced heap sort, which is a sort that uses heaps. Although heapsort is a good algorithm, a great implementation of quicksort, which we’ll discuss later, is usually quicker. However, the heap can be used in a variety of ways, and in this post, I’d want to show you how to use the heap to build a priority queue.
What is Priority Queue?
A data structure for handling elements with values called keys.
Normal queues implement FIFOs. Therefore, the element that came in first is always the first to go out, regardless of the priority. However, in the priority queue, the order of exit is determined according to the priority. Even if it is the last element to enter, if it has the highest priority, it is the first to go out.
Types of Priority Queue
Like the heap, the priority queue is divided into a max priority queue and a min priority queue. Literally, the highest priority queue outputs in the order of highest priority, and the lowest priority queue outputs the outputs in the order of lowest priority. We will focus on the max priority queue here.
Example usage of priority queue
1. Shared computer task sequence (max priority queue)
In general, in order to sequence tasks on a shared computer, tasks must be executed according to their priority. Therefore, if you use a maximum priority queue to determine this order, you can run tasks in the order of importance.
2. Event Responsive Simulator
Simulations must be in chronological order of occurrence, as the simulation of one event may affect other simulated events in the future. Therefore, simulation can be performed using the simulation program minimum priority queue.
Basic Operation
Insert(S, x)
Inserts a new element x into the maximum priority queue (S).
2. Maximum(S)
Returns the element with the largest key value in the maximum priority queue (S).
3. Extract-Max(S)
Removes the element with the largest key value from the maximum priority queue (S).
4. Increase-Key(S, x, k)
Increase the key value of element x to k. However, it is assumed that k does not become smaller than the original key value of x.
Conclusion
If you look at the above four functions, you can see that all but one have the same thing in common. The execution time is all O(log n). In fact, a priority queue can be created even if the heap is not used. However, the fatal disadvantage of the priority queue using other data structures is that the time required for inserting is too much in O(n).
As you can see from the picture above, there is a huge difference between O(log n) and O(n). So many people implement priority queues as heaps.
