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.

About these ads

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

    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]
    
  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[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);
    }
    
    
  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')
    	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()
    
  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.

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: