The preface

A normal queue is a first-in, first-out data structure, with elements appended at the end of the queue and removed from the head of the queue. In priority queues, elements are assigned priority. When an element is accessed, the element with the highest priority is deleted first. Priority queues have the behavior characteristics of first in (largest out). It is usually implemented using heap data structures.

1, the preface

What is a priority queue?

Before we begin, it’s worth discussing what a priority queue really is. A priority queue is a queue in which each item has a “priority” that can be compared to other queue items. Once an item is dequeued, it pops out of the queue whenever it has the highest priority. Therefore, if we consider the standard queue to be first-in, first-out (FIFO) and the stack type to be last-in, first-out (LIFO), the priority queue is… Well. . Whatever is entered, the highest priority is first out!

The priority can be complex, as we will soon see when implementing a custom comparator, but at its simplest it can be a number, and the smaller the number (for example, 0 is the highest), the higher the priority.

Priority queues have many uses, but they are most common when doing “graph traversal” work, because you can quickly identify the nodes with the highest/lowest “cost” and so on. It’s not too important. What you really need to know is that there is a queue that prioritizes items for you!

3. Priority queue basics

using System.Collections.Generic;

PriorityQueue<string.int> queue = new PriorityQueue<string.int> (); queue.Enqueue("Item A".0);
queue.Enqueue("Item B".60);
queue.Enqueue("Item C".2);
queue.Enqueue("Item D".1);

while (queue.TryDequeue(out string item, out int priority))
{
    Console.WriteLine($"Popped Item : {item}. Priority Was : {priority}");
}
Copy the code

Popped Item : Item A. Priority Was : 0
Popped Item : Item D. Priority Was : 1
Popped Item : Item C. Priority Was : 2
Popped Item : Item B. Priority Was : 60
Copy the code

4. Use custom comparators

The above example is relatively easy to understand because priorities are just integers. But what if we have complex logic about how to derive priorities? We can build this logic ourselves and still use integer precedence, or we can use a custom comparator. Let’s do the latter!

Suppose we are building a banking application. This is a bank in central London, so priority is given to anyone whose first name is “Sir”. Even if they show up at the back of the queue, they should be served first (I know this is disgusting… Present situation! .

The first thing we need to do is find a way to compare titles. To that end, this code should solve the problem:

class TitleComparer : IComparer<string>
{
    public int Compare(string titleA, string titleB)
    {
        var titleAIsFancy = titleA.Equals("sir", StringComparison.InvariantCultureIgnoreCase);
        var titleBIsFancy = titleB.Equals("sir", StringComparison.InvariantCultureIgnoreCase);


        if (titleAIsFancy == titleBIsFancy) //If both are fancy (Or both are not fancy, return 0 as they are equal)
        {
            return 0;
        }
        else if (titleAIsFancy) //Otherwise if A is fancy (And therefore B is not), then return -1
        {
            return - 1;
        }
        else //Otherwise it must be that B is fancy (And A is not), so return 1
        {
            return 1; }}}Copy the code

We simply inherit from IComparer, where T is the type we are comparing. In our case, it’s just a simple string. Next, we check that each incoming string is the word “Mr.”. Then order on that basis. In general, the comparator should return the following:

• Returns 0 if the two items based on are equal
• If the first item is “higher” or has a higher priority than the second, -1 is returned
• Return 1 if the second item has a higher priority than the first. Now, when we create the queue, we can simply pass the new comparator like this:

PriorityQueue<string.string> bankQueue = new PriorityQueue<string.string> (new TitleComparer());
bankQueue.Enqueue("John Jones"."Sir");
bankQueue.Enqueue("Jim Smith"."Mr");
bankQueue.Enqueue("Sam Poll"."Mr");
bankQueue.Enqueue("Edward Jones"."Sir");

Console.WriteLine("Clearing Customers Now");
while (bankQueue.TryDequeue(out string item, out string priority))
{
    Console.WriteLine($"Popped Item : {item}. Priority Was : {priority}");
}
Copy the code

The following output is displayed:

Clearing Customers Now
Popped Item : John Jones. Priority Was : Sir
Popped Item : Edward Jones. Priority Was : Sir
Popped Item : Sam Poll. Priority Was : Mr
Popped Item : Jim Smith. Priority Was : Mr
Copy the code

5. When do you prioritize?

Console.WriteLine($"Comparing {titleA} and {titleB}");
Copy the code

Comparing Mr and Sir Comparing Mr and Sir Comparing Sir and Sir Clearing Customers Now Comparing Mr and Mr Comparing Sir  and Mr Popped Item : John Jones. Priority Was : Sir Comparing Mr and Mr Popped Item : Edward Jones. Priority Was : Sir Popped Item : Sam Poll. Priority Was : Mr Popped Item : Jim Smith. Priority Was : MrCopy the code

6, the source code

Having said that, the source code is certainly open, so you’re welcome to understand and comment for yourself! You can see in the following position in 2015 PriorityQueue original proposal: HTTPS: / / github.com/dotnet/runtime/issues/14032. Most importantly, it gives the community insight into how and why decisions are made. Not only that, it provides benchmarks for different methods and explains why certain things were not included in the first release of the Priority Queue API. This is really great stuff!

7, summary