[m-users.] priority search queue ADT

Matthias G├╝demann matthias.guedemann at googlemail.com
Fri Oct 24 06:59:14 AEDT 2014


Hello @all,

I implemented a priority search queue in Mercury. This is similar to
pqueue.m (priority queue), but also allows to look up keys, delete keys
and adjust the priorities of keys.

It follows closely the implementation described by Ralf Hinze in his
ICFP 2001 paper "A Simple Implementation Technique for Priority Search
Queues". Peeking at the element with highest priority is in O(1),
inserting, deletion, key look-up and adjusting a priority is in
O(log(n)). In contrast to the 234-trees of pqueue.m, it uses
weight-balanced trees, so it might have slightly larger constants for
the same operations.

I did this to implement an efficient, fully declarative Dijkstra's
single source, shortest path search on digraphs. The current test cases
are the example in the paper and 3 project Euler problems
(81/82/83). Currently, I have not yet decided on any license, in general
I'd lean towards BSD, but it would be no problem to put into public
domain if necessary[1]. I'd be happy to see this as a standard ADT in
Mercury.

 - Are you interested in this?
 - What is necessary to have it integrated in the library or as an
   extra?

Best regards,
Matthias

Footnotes: 
[1]  http://mercurylang.org/development/contributions.html



More information about the users mailing list