Implementing priority queue in Raku

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:

C
B
D
A

→ GitHub repository
→ Navigation to the Raku challenges post series

Leave a Reply Cancel reply