## Priority Queues

### May 5, 2009

We represent a node as a four-slot vector: rank, item, left child, and right child. Access functions are written as macros so they will be inlined for speed; there is no need for update functions since nodes are immutable:

`(define-syntax pq-rank (syntax-rules () ((_ pq) (vector-ref pq 0))))`

(define-syntax pq-item (syntax-rules () ((_ pq) (vector-ref pq 1))))

(define-syntax pq-lkid (syntax-rules () ((_ pq) (vector-ref pq 2))))

(define-syntax pq-rkid (syntax-rules () ((_ pq) (vector-ref pq 3))))

There is a single, distinguished node representing the empty priority queue, with rank zero, and a predicate to identify it:

`(define pq-empty (vector 0 'pq-empty 'pq-empty 'pq-empty))`

(define (pq-empty? pq) (eqv? pq pq-empty))

The fundamental operation is `pq-merge`

, which operates in two phases. A winding phase descends the tree, calling `pq-merge`

recursively down the right spine of the tree. The unwinding phase calls a helper function to swap children as needed. Recursion ends when either of the priority queues being merged is empty.

`(define (pq-merge lt? p1 p2)`

(define (pq-swap item lkid rkid)

(if (< (pq-rank rkid) (pq-rank lkid))

(vector (+ (pq-rank rkid) 1) item lkid rkid)

(vector (+ (pq-rank lkid) 1) item rkid lkid)))

(cond ((pq-empty? p1) p2)

((pq-empty? p2) p1)

((lt? (pq-item p2) (pq-item p1))

(pq-swap (pq-item p2) (pq-lkid p2)

(pq-merge lt? p1 (pq-rkid p2))))

(else (pq-swap (pq-item p1) (pq-lkid p1)

(pq-merge lt? (pq-rkid p1) p2)))))

The pq-insert, pq-first and pq-rest functions all call pq-merge trivially:

`(define (pq-insert lt? x pq)`

(pq-merge lt? (vector 1 x pq-empty pq-empty) pq))

`(define (pq-first pq)`

(if (pq-empty? pq)

(error 'pq-first "empty priority queue")

(pq-item pq)))

`(define (pq-rest lt? pq)`

(if (pq-empty? pq)

(error 'pq-rest "empty priority queue")

(pq-merge lt? (pq-lkid pq) (pq-rkid pq))))

In addition to the requirements of the exercise, we provide conversions to and from lists and a sorting function based on priority queues:

`(define (list->pq lt? xs)`

(let loop ((xs xs) (pq pq-empty))

(if (null? xs) pq

(loop (cdr xs) (pq-insert lt? (car xs) pq)))))

`(define (pq->list lt? pq)`

(let loop ((pq pq) (xs '()))

(if (pq-empty? pq) (reverse xs)

(loop (pq-rest lt? pq) (cons (pq-first pq) xs)))))

`(define (pq-sort lt? xs)`

(pq->list lt? (list->pq lt? xs)))

And here is a simple demonstration of priority queues:

`> (pq-sort < '(3 7 8 1 2 9 6 4 5))`

(1 2 3 4 5 6 7 8 9)

You can run the assembled code at http://codepad.org/V8v6If7Z.

[…] Praxis – Priority Queues By Remco Niemeijer Today’s Programming Praxis problem is about priority queues. Specifically, we have to implement one using a […]

My Haskell solution (see http://bonsaicode.wordpress.com/2009/05/05/programming-praxis-priority-queues/ for a version with comments):

data PQueue a = Node Int a (PQueue a) (PQueue a) | Empty

rank :: PQueue a -> Int

rank Empty = 0

rank (Node r _ _ _) = r

node :: a -> PQueue a -> PQueue a -> PQueue a

node i l r = if rank l > rank r then node i r l else Node (1 + rank r) i l r

merge :: (a -> a -> Bool) -> PQueue a -> PQueue a -> PQueue a

merge _ Empty q = q

merge _ q Empty = q

merge p l@(Node _ il _ _) r@(Node _ ir lc rc) =

if p ir il then node ir lc (merge p l rc) else merge p r l

insert :: (a -> a -> Bool) -> a -> PQueue a -> PQueue a

insert p i = merge p (node i Empty Empty)

fromList :: (a -> a -> Bool) -> [a] -> PQueue a

fromList p = foldr (insert p) Empty

toList :: (a -> a -> Bool) -> PQueue a -> [a]

toList _ Empty = []

toList p (Node _ i l r) = i : toList p (merge p l r)

pqSort :: (a -> a -> Bool) -> [a] -> [a]

pqSort p = toList p . fromList p

main :: IO ()

main = print $ pqSort (<) [3, 7, 8, 1, 2, 9, 6, 4, 5] [/sourcecode]

A C solution, dealing with strings:

…and a Python variation on the same theme:

I struggled with the Python version quite a bit, on a conceptual level: couldn’t get my head around what objects to define. I’d start writing the tree and its methods, and realise I needed the methods to sometimes work on the tree, and sometimes on the nodes, which were distinct objects.

In the end, I had an epiphany when I read the ‘OOP style vs. recursive style’ paragraph on this page: http://cslibrary.stanford.edu/110/BinaryTrees.html

I did find this approach a bit artificial though, and somehow find the C way of dealing with self-referencing data structures more natural and elegant. That said, re-reading my C code after I’d worked on the Python version, I find I’d do a number of things differently now. I’ve often read that learning other languages will make one a better programmer, but that’s the first time I’ve experienced it first-hand in such an obvious way.