Site icon R-bloggers

Deriving a Priority Queue from a Plain Vanilla Queue

[This article was first published on Exegetic Analytics » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Following up on my recent post about implementing a queue as a reference class, I am going to derive a Priority Queue class.

Inheritance

The syntax for Reference Class inheritance is quite intuitive.

PriorityQueue <- setRefClass("PriorityQueue",
                             contains = "Queue",
                             fields = list(
                               priorities = "numeric"
                             ),
                             methods = list(
                               push = function(item, priority) {
                                 'Inserts element into the queue, reordering according to priority.'
                                 callSuper(item)
                                 priorities <<- c(priorities, priority)
                                 #
                                 order = order(priorities, decreasing = TRUE, partial = size():1)
                                 #
                                 data <<- data[order]
                                 priorities <<- priorities[order]
                               },
                               #
                               pop = function() {
                                 'Removes and returns head of queue (or raises error if queue is empty).'
                                 if (size() == 0) stop("queue is empty!")
                                 priorities <<- priorities[-1]
                                 callSuper()
                               })
)

We need to modify only two of the methods. The most important of these is insert(), which is where all of the important stuff happens! I’ve added an additional parameter, priority, which gives the relative importance of the item to be inserted (with larger values indicating greater importance). The items are sorted according to priority, where items of higher priority are shifted to the front of the queue. Amongst items which have the same priority, the order of insertion is retained. The pop() method also needs modification: when items are removed from the queue, the corresponding priority is also discarded.

Priority Queue in Action

We create an instance of the Priority Queue and then insert four items with varying levels of importance.

> q4 <- PriorityQueue$new()
> 
> q4$push("first", 1)
> q4$push("second", 2)
> q4$push("third", 1)
> q4$push("fourth", 3)

According to the logic outlined above, the item “fourth” should move to the front of the queue since it has the highest priority. It will be followed by “second” which has next highest priority. Finally we have “first” and “second”, which have the same priority and thus retain the order in which they were inserted.

> q4$priorities
[1] 3 2 1 1
> q4$data
[[1]]
[1] "fourth"

[[2]]
[1] "second"

[[3]]
[1] "first"

[[4]]
[1] "third"

Next we can start extracting items from the queue. As expected, item “fourth” comes out first, followed in turn by “second”, “first” and “third”. The methods which were inherited without modification work as expected.

> q4$pop()
[1] "fourth"
> q4$priorities
[1] 2 1 1
> 
> q4$pop()
[1] "second"
> q4$peek()
[1] "first"
> q4$poll()
[1] "first"
> 
> q4$pop()
[1] "third"
> q4$priorities
numeric(0)
> q4$poll()
NULL

To leave a comment for the author, please follow the link and comment on their blog: Exegetic Analytics » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.