# Implementing priority queue in Raku

Let us implement a simple priority queue in the Raku programming language.

Let us implement a simple priority queue in the Raku programming language. This post solves the problem 2 of the Week 18 of the Perl Weekly Challenge.

The queue implements three methods: `is_empty` telling if the queue is empty, `insert_with_priority` to add data attributed with a numeric priority value, and `pull_highest_priority_element` to get the element which has higher priority, or if there are more than one, then the element which was added first.

Here is the implementation of the corresponding class:

```class PriorityQueue {
has %!queue;
has \$!count = 0;

method is_empty() {
%!queue.elems == 0
}

method insert_with_priority(\$data, \$priority) {
%!queue{\$!count++} = {
data => \$data,
priority => \$priority,
};
}

method pull_highest_priority_element() {
my @sorted = %!queue.sort: {.value<priority>, -.key};
(%!queue{@sorted[*-1].key}:delete)<data>;
}
}```

An instance of this class is using the `%!queue` hash to store data and the counter `\$!count`, which increments with each inserted item.

```has %!queue;
has \$!count = 0;```

The key of the storage is the value of `\$!count` at the moment of insertion. Its values are the hashes containing the two pairs: `data` and `priority`:

```%!queue{\$!count++} = {
data => \$data,
priority => \$priority,
};```

Such two-layer architecture of the storage allows easy access when we need to remove the data item after it is pulled out from the queue.

To find the most prioritised item, we sort the storage by two parameters: priority and insertion number:

`my @sorted = %!queue.sort: {.value<priority>, -.key};`

Then, the last element is taken and immediately deleted from the storage. Raku’s `:delete` adverb removes the element from the hash and returns it, so we do not need any temporary variables:

`(%!queue{@sorted[*-1].key}:delete)<data>;`

Note 1. Raku’s `sort` routine accepts more than one sort element. This is exactly what we need to first sort by priority and then additionally sort by the order of insertion.

Note 2. To sort reversely, the simple solution is to negate the numeric value of the key: `-.key`.

Note 3. Calling `pull_highest_priority_element` on an empty queue generates an error. Thus, you must always check if it is empty or implement the check inside the pulling method.

Note 4. This code sorts the whole data storage, which is not optimal for big data sets. If you want a queue containing a lot of data, you should reorganise the `PriorityQueue` class so that it keeps additional helper attributes to quickly find the needed data without scanning and sorting the whole storage.

The implementation of the `is_empty` method is trivial:

`%!queue.elems == 0`

Finally, we can use the class. Let’s insert a few elements with different priorities and make a loop to pull the data in the correct order:

```my \$pq = PriorityQueue.new;

\$pq.insert_with_priority('A', 10);
\$pq.insert_with_priority('B', 20);
\$pq.insert_with_priority('C', 30);
\$pq.insert_with_priority('D', 20);

say \$pq.pull_highest_priority_element while !\$pq.is_empty;```

The program prints the data in the following order:

`CBDA`