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.
Programming Praxis 
[…] 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:
#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[100]; 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); }…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') nameslist = f.read().split() f.close() myTree = lTree() for n in nameslist: myTree.insert(n) print 'Sorted names list:' while myTree.root: print myTree.del_min()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.