I am so excited for my first post about data structures used in games. One of my professors used to say that applications are nothing but *data structures* and *algorithms *together. I don’t know if this theory still holds, but data structures are quite important parts of any kind of application including games. As a first topic, I’d like to write about **Priority Queue**, since it is not part of the **C#’s Collection API**.

*Priority Queue* is a special type of a Queue. Whereas a standard Queue works on **first in, first out (FIFO) **principle, a priority queue works with priorities assigned to each item. **High priority items are dequeued before** **the elements with low priority.**

### Applications of Priority Queue

Before going in details of *Priority Queue*, let’s see in which cases we can use it.

#### Example Scenario

I have mostly used a *priority queue* for solving *AI* problems in my games. Let’s say we are creating a cool *bot for a board game*. This game provides you **three **moves at each turn. The bot will decide which order of the moves are **the most valuable** ones for the next turn.

As a simple solution to this AI problem, we can have a *tree* structure. The *root *represents the current state of the board. It will have many *children *representing the three moves to the available positions (in my game, it was around** 270 children**). Then, at **every child** we will have other possible moves to the available positions. At the end, we will evaluate the value of each chain of moves in the leaves of this tree.

I could *keep some kind of score property* in the nodes, then *sort the leaves of the tree*, based on the score. Then I could pick the highest one. However, I preferred to use a *Priority Queue*. So, I have placed the nodes with their *score *as a *priority*. Why?

- It helped me to optimize this query.
**Instead of evaluating 270 children**, I have traversed only**the most prominent ones**. - In order to create
**different levels of difficulty**. Based on the chosen difficulty, priority queue gave me*the second best or the third best*set of prominent children. - I have also wanted to
**hide sorting and choosing best candidate behaviors**from the evaluation of the tree. It was already quite complex and I didn’t want it to be more complex. - It was
**reusable**for other bot implementations.

So I am quite happy with the results.

#### Other possible usages of Priority Queues

**Dijkstraâ€™s Shortest Path Algorithm**can be implemented using Priority Queue.- It can be also used to implement
**Huffman’s compression algorithm**. **A* path finding algorithm**- A sorting algorithm called
**Heap Sort**is implemented using Priority Queue. - It is possible to give more examples like
**Prim’s algorithm**, or**Load Balancing algorithms**. Simply, we can use it everywhere that is an application of queue where*priority*is involved.

### So, How to Implement a Priority Queue?

Well, let’s know our requirements first;

- We need items with priorities.
- These items will be inserted into somewhere, a container or a list.
- We should be able to reach or delete the element with the
*highest priority*.

public interface IPriorityQueue<T> { /// Inserts and item with a priority void Insert(T item, int priority); /// Returns the element with the highest priority T Top(); /// Deletes and returns the element with the highest priority T Pop(); }

We can obviously have more features but let’s keep it simple.

#### Items with Priorities

I guess, this is easy. We can just have a struct with two fields.

struct Item { int element; int priority; }

#### Insert

In order to support insert operation we can use a *List<Item>*. It will take only *O(1) *time, so it is not bad.

#### Top() and Pop()

Using *List *structure was good for *Insert *method, but for *Top() *and *Pop() *methods, it may not be the best. Because we need to sort the list based on the priorities, then pick the first or the last element based on the sorting order.

If we use a *Linked List*, it would take less time for *Pop()*. However, I believe that our most important method here is the *Top()*. Therefore, we should be looking for optimizing it.

#### What About Using Heaps?

When it comes to **Priority Queue **implementation, *Heaps *are the best candidate. It provides much better performance then lists. Only drawback is the Insert performance — It would be *O(log n)* — which is not a big loss. **Pop()** can be done in *O(log n)* and most importantly **Top()** will be in *O(1)* time.

As far as I remember from the school years, we can even make the Insert in *O(1)* time, if we use a *Fibonacci heap*. Since it is harder to implement, I will fork from an implementation I found on GitHub done by squezy.

There is no need to go into details for heaps, because — trust me — it is not a short topic. In addition to that, you don’t need to know how they are implemented. However, a little short introduction would help to understand the next step.

#### Briefly, What the Heck is a Heap?

There are two type of heaps I would like to introduce. The first one is a Binary heap. It is a binary tree which satisfies the * min-heap property* — the value of each node is greater than or equal to the value of its parent and the root has the minimum value. — or

*which is not so hard to guess, it is the opposite of min-heap property. So, the operations like insert or delete, should maintain this properties.*

**max-heap property**While *Binary heap* maintains the heap property all the time, there are other heaps which are more relaxed. Fibonacci Heap is a good example which has better *amortized complexity* due to its flexible nature. It does the operations lazily, so most of the operations are in *O(1)* time. In case you are curious, it would be sufficient to read its Wikipedia explanation.

#### Back to the Priority Queue

Since we will implement the *Priority Queue* using *Fibonacci Heaps*, we should be aware of that, it maintains a * min-heap property*. Therefore, the priority being represented by a lower number, would have a higher priority. For instance, let’s think a set like {1, 4, 3, 5}. The highest priority will be ‘1’ in this set.

public class PriorityQueue<TElement, TPriority> : IPriorityQueue<TElement, TPriority> where TPriority : IComparable<TPriority> { private readonly FibonacciHeap<TElement, TPriority> heap; public PriorityQueue(TPriority minPriority) { heap = new FibonacciHeap<TElement, TPriority>(minPriority); } public void Insert(TElement item, TPriority priority) { heap.Insert(new FibonacciHeapNode<TElement, TPriority>(item, priority)); } public TElement Top() { return heap.Min().Data; } public TElement Pop() { return heap.RemoveMin().Data; } }

As you see in the above implementation, it is just so easy to implement a priority queue backed with a *Fibonacci heap*. In case you want to see the whole code, here is the link for the repository. If you would like to use this in your projects, just add this line to your dependencies in *manifest.json*.

"com.erdiizgi.datastructures": "https://github.com/erdiizgi/DSUnity.git#v0.0.2"

You can have different implementations of the *IPriorityQueue*, and if you bind the implementations using a *DI Container* like Zenject, you can get the maximum work-ability with this interface.

## Conclusion

Priority queue can be useful when your game requires some kind of decision making process. It can hide some unnecessary complexity and they can be quite performant when they are backed by Fibonacci Heaps.

*C# Collection API* doesn’t contain these data structures out of the box, but there are a lot of implementations you can find online. I am planning to maintain this Data Structures repository with the new posts. In case you have questions to ask, please drop me a comment below. Feel free to contribute to the repository as well. (please use the **development **branch for the pull requests)

## Droid

3rd May 2019 — 7:01 am

Hi, where can I see my manifest file? Can you explain that part a bit more?

I have already downloaded and imported the Unitypackage file from github, but I want to use the Unity Package Manager.

## erdiizgi

3rd May 2019 — 8:47 am

Hi, I am not aware of any way to edit manifest.json from the Unity Editor’s Package Manager.

However, you can go to your project’s root folder and see a folder named ‘Packages’, and find your manifest.json there.

you can add “com.erdiizgi.datastructures”: “https://github.com/erdiizgi/DSUnity.git#v0.0.2” to the dependencies, and you will have the package without any additional effort. I hope it helps.