Deriving a Priority Queue from a Plain Vanilla Queue

November 25, 2013
By

(This article was first published on Exegetic Analytics » R, and kindly contributed to R-bloggers)

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 his blog: Exegetic Analytics » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.