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

Photo by Scott Graham on Unsplash

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.

Photo by ThisisEngineering RAEng on Unsplash

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.

Buy me a Coffee

--

--

--

Full Stack Dev

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Git 101: A Guide to Help You Started

Opyn Ecosystem Grants

Lessons learned from building a production ready app in Django

Running PostgreSQL Database in a Docker Container

Selenium: Reflections about Cluster Economics

This Week I Learned #7

Java null checking with Optional

10 Best Python IDEs and Code Editors to use in 2021

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
ki hyun Lee

ki hyun Lee

Full Stack Dev

More from Medium

Scheduling algorithms in Operating system

ULIDs and Primary Keys

Overview: Merge Requests

Git Feature — A new methodology to manage your development work