How to use a priority queue in Julia

Overview

A PriorityQueue is a type of queue in which there is a value representing the priority associated with each element. The objects in the queue are processed based on the priority value.

In PriorityQueue, multiple identical elements are not allowed, but multiple elements can have the same priority value.

By default, the priority order of the PriorityQueue is Base.Order.Forward, which represents the ascending order. We can also change this while creating the PriorityQueue object by passing any one of the below options

  1. Base.Order.Forward: This represents the ascending order.
  2. Base.Order.Reverse: This represents the descending order.

Example

Below is a sample code for using a PriorityQueue in Julia:

using DataStructures
# create a new PriorityQueue
pq= PriorityQueue{String, Int}(Base.Order.Reverse);
# enqueue! - insert the key k into pq with priority v
enqueue!(pq, "ten", 10);
enqueue!(pq, "five", 5);
enqueue!(pq, "fifteen", 15);
println("\nThe priorityqueue : $(pq)")
println("\nChanging the priority value of ten to 0")
# Change the priority of an existing key
pq["ten"] = 0;
println("\nThe priorityqueue : $(pq)")
# peek -- return the lowest priority key and value without removing it
println("\nThe loweset priority element is $(peek(pq))")
## dequeue! -- remove and return the lowest priority key
println("\nRemoving loweset priority element: $(dequeue!(pq))")  
println("\nThe priorityqueue : $(pq)")

Explanation

  • Line 3: We create a PriorityQueue object with the name pq. We set the order of the elements as Base.Order.Reverse, which means that the value with a high priority value will be considered the lowest priority element.
  • Lines 6–8: We use the enqueue! method to insert three elements into the pq. The elements in the queue are ordered based on the priority value.
  • Line 14: We change the priority value of the element ten to 0.
  • Line 19: We use the peek method to get the element with the lowest priority (the first element of the queue).
  • Line 21: We use the deque! method to remove the element with the lowest priority (first element of the queue).

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)