## Pairing Heaps

### August 14, 2009

We represent a node in a priority queue as a list with the item in its car and the multi-way tree in its cdr. The empty priority queue is represented by the null list:

`(define pq-empty '())`

(define pq-empty? null?)

`Pq-first`

, `pq-merge`

and `pq-insert`

are all trivial:

`(define (pq-first pq)`

(if (null? pq)

(error 'pq-first "can't extract minimum from null queue")

(car pq)))

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

(cond ((null? p1) p2)

((null? p2) p1)

((lt? (car p2) (car p1))

(cons (car p2) (cons p1 (cdr p2))))

(else (cons (car p1) (cons p2 (cdr p1))))))

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

(pq-merge lt? (list x) pq))

`Pq-rest`

deletes the item at the root of a node, returning the tail after submitting it to the two-pass pair-wise merge algorithm:

`(define (pq-merge-pairs lt? ps)`

(cond ((null? ps) '())

((null? (cdr ps)) (car ps))

(else (pq-merge lt? (pq-merge lt? (car ps) (cadr ps))

(pq-merge-pairs lt? (cddr ps))))))

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

(if (null? pq)

(error 'pq-rest "can't delete minimum from null queue")

(pq-merge-pairs lt? (cdr pq))))

We provide conversions to and from lists and a sorting function based on priority queues; the functions below are copied unchanged from the prior exercise:

`(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)))

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 code at http://programmingpraxis.codepad.org/NHfZUl38.

Pages: 1 2

[…] Remco Niemeijer Righty, I’m back from vacation so let’s get right back to business. In today’s Programming Praxis problem we have another data structure to implement. Let’s get […]

My Haskell solution (see http://bonsaicode.wordpress.com/2009/08/14/programming-praxis-pairing-heaps/ for a version with comments):

How’s this for a Programming Praxis: Fix your damn website so it does not break in Opera when you get 1/3 of the way down the front page.

[…] […]

my implementation in C

[…] a program to implement the algorithm described above, using the Scheme programming language. First, here is a library implementation of priority queues using the pairing heap […]