Priority Queue:

date posted: 2020-01-15

Priority Queue

There isn't really much to talk about.

As the name speaks for itself it is a Queue that has priorities.

Queue is a data structure that holds FIFO or LILO principle, simply think of it as a line for the bathroom. If your first in line you will get stuff out first.

Now lets add some extra properties

1. there exists priority(rank) for all elements
2. Higher priority gets our first.
3. if elements have same priorities, element which came first gets out first.
4. elements musts be comparable

Now we know what Priority Queue is, what can it do?

It has 3 operations:

• Insert
• get highest priority
• delete highest priority

Priority Queue can be implements using a list.
for example: [5, 2, 6, 1, 8].
greater the number higher the prioirty.

when we want insert new element, say new_element = 10 no matter its prioirty we append it to end of the list therefore [5, 2, 6, 1, 8, 10] so no matter what O(n) = 1, perfect!

Now we say we want to delete or look for highest prioirty, then notice since 10 is at the end of the list we have to do a linear search... giving us O(n) = n.

Reason we use prioirty queue is to get element with highest prioirty as fast as we can but using a list does not seem to help us reach our goal hence Heap is introduced.

Now by storing elements into Max-heap or Min-heap structure we know that our first value (root node) has the highest priority. I will cover Heap in next section as it is separate data structure that has many applications other than for prioirty queues.

Applications

1. CPU scheduling
2. In Dijkstra's shortest path algorithm
3. Huffman coding
4. Best First Search
5. Minimum spanning Tree algorithms
6. Load balancing on servers