## 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.

Pages: 1 2

### 5 Responses to “Priority Queues”

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

2. Remco Niemeijer said

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]

3. Jebb said

A C solution, dealing with strings:

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
int rank;
char *name;
struct node *left;
struct node *right;
};

void *del_min(struct node **, char *);
struct node *insert_value(char *, struct node *);
struct node *merge(struct node *, struct node *);
void print_node(struct node *node);
int debug_print_tree(struct node *);
void swap(struct node **, struct node **);
struct node *make_node(char *);
void del_node(struct node *);

int main()
{
struct node *root = NULL;
char c, *cp;
char buffer;
int i;
cp = buffer;
while ((c = getchar()) != EOF) {
if ((c != '\n') && (buffer - cp < 98))
*cp++ = c;
else if (c == '\n') {
*cp = '\0';
root = insert_value(buffer, root);
cp = buffer;
}
}
printf("Sorted names list:\n");
while (root != NULL) {
del_min(&root, buffer);
printf("%s\n", buffer);
}
return 0;
}

void *del_min(struct node **root, char *first)
/* Returns the first (in alphabetical order) name in the tree,
* and deletes it, merging the two sub-trees
* We need to pass the address of the tree root (struct node **),
* as the tree will have a new root after running this function*/
{
struct node *tmp_root;
strcpy(first, (*root)->name);
tmp_root = merge((*root)->left, (*root)->right);
del_node(*root);
(*root) = tmp_root;
}

struct node *insert_value(char *name, struct node *tree)
{
struct node *newStudent, *newRoot;
newStudent = make_node(name);
newRoot = merge(newStudent, tree);
return newRoot;
}

struct node *merge(struct node *treeA, struct node *treeB)
{
if (treeA == NULL) return treeB;
if (treeB == NULL) return treeA;
if (strcmp(treeB->name, treeA->name) < 0)
swap(&treeA, &treeB);
treeA->right = merge(treeA->right, treeB);
/* The right child is guaranteed not to be NULL, but
* we don't know that the left child is not NULL!
* The rank of the NULL node is taken to be -1, so it will be
* swapped with a childless, non-NULL node */
if (treeA->right->rank > (treeA->left ? treeA->left->rank : -1)) {
swap(&(treeA->right), &(treeA->left));
}
if (treeA->right == NULL)
treeA->rank = 0;
else
treeA->rank = treeA->right->rank + 1;
return treeA;
}

void print_node(struct node *mynode)
{
printf("Node - rank : %d ; name : %s\n", mynode->rank, mynode->name);
if (mynode->left)
printf("\tleft: %s\n", mynode->left->name);
if (mynode->right)
printf("\tright: %s\n", mynode->right->name);
}

int debug_print_tree(struct node *root)
/* Returns the number of nodes printed */
{
if (root == NULL)
return 0;
print_node(root);
printf("----------\n");
return 1 + debug_print_tree(root->left) + debug_print_tree(root->right);
}

void swap(struct node **nodeA, struct node **nodeB)
{
struct node *tmpnode;
tmpnode = *nodeA;
*nodeA = *nodeB;
*nodeB = tmpnode;
}

struct node *make_node(char *new_student)
{
struct node *tmp_node;
tmp_node = (struct node *)malloc(sizeof(struct node));
tmp_node->rank = 0;
tmp_node->name = strdup(new_student);
tmp_node->left = NULL;
tmp_node->right = NULL;
return tmp_node;
}

void del_node(struct node *oldnode)
{
free(oldnode->name);
free(oldnode);
}

```
4. Jebb said

…and a Python variation on the same theme:

```#!/usr/bin/python2.7
import copy
class _lNode(object):
def __init__(self, value):
self.key = value
self.rank = 0
self.left = None
self.right = None

def _merge(treeA, treeB):
# This function isn't robust, it will produce circular references
# when merging a tree with a part of itself for example
# Hopefully safe for use with the methods in the lTree class, though
if treeA == None: return treeB
if treeB == None: return treeA
if treeB.key < treeA.key:
treeB, treeA = treeA, treeB
treeA.right = _merge(treeA.right, treeB)
if (treeA.left and treeA.left.rank or -1 ) < treeA.right.rank:
treeA.left, treeA.right = treeA.right, treeA.left
if treeA.right:
treeA.rank = treeA.right.rank + 1
else:
treeA.rank = 0
return treeA

class lTree(object):
def __init__(self):
self.root = None
def insert(self, value):
tmpNode = _lNode(value)
if self.root == None:
self.root = tmpNode
return
else:
self.root = _merge(self.root, tmpNode)
def del_min(self):
if self.root == None:
return None
else:
tmpVal = self.root.key
self.root = _merge(self.root.left, self.root.right)
return tmpVal
def debug_print(self):
#begin helper function
def _h_debug_print(node):
if node == None:
return
else:
print 'Value: %s, rank: %d' % (node.key, node.rank)
_h_debug_print(node.left)
_h_debug_print(node.right)
#end helper function
if self.root == None:
print 'Empty queue!'
return
else:
_h_debug_print(self.root)

if __name__ == "__main__":
f = open('test', 'r')
f.close()
myTree = lTree()
for n in nameslist: myTree.insert(n)
print 'Sorted names list:'
while myTree.root:
print myTree.del_min()
```
5. Jebb said

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.