Re: [Caml-list] Priority queues

Re: [Caml-list] Priority queues

[Radu Grigore]

On Friday, July 1, 2011 11:33:11 AM UTC+1, Andrew wrote:
> > - or your priority queue does not provide such an operation, and you
> > simply add another entry for y in the priority queue, with a different
> > key. It means you have now several entries for y in the priority queue.
> > The better will be extracted first; the others will be ignored when they
> > are extracted later. Complexity is now O(E log(V)).
> 
> Just an extra question though: How come it's not O(E log (E))?
> You could end up pushing as much as one new element in 
> your heap per edge, couldn't you?

If you use a Set of (distance, vertex) pairs together with min_elt then you can simulate decrease-key using remove followed by add.

Re: [Caml-list] Priority queues

[Brian Hurt]

On Fri, 1 Jul 2011, Radu Grigore wrote:

> On Friday, July 1, 2011 11:33:11 AM UTC+1, Andrew wrote:
>>> - or your priority queue does not provide such an operation, and you
>>> simply add another entry for y in the priority queue, with a different
>>> key. It means you have now several entries for y in the priority queue.
>>> The better will be extracted first; the others will be ignored when they
>>> are extracted later. Complexity is now O(E log(V)).
>>
>> Just an extra question though: How come it's not O(E log (E))?
>> You could end up pushing as much as one new element in
>> your heap per edge, couldn't you?
>
> If you use a Set of (distance, vertex) pairs together with min_elt then 
> you can simulate decrease-key using remove followed by add.

You could also keep a map of vertices to distances, so you can update the 
distance of a vertex that is not the minimum element without knowing what 
it's previous distance was.  Something like:

module PQ(Key: Map.Ordered)(Data: Map.Ordered) = struct
 	module X = struct
       		type t = Key.t * Data.t;;
 	        let compare (k1, d1) (k2, d2) =
 			let c = Key.compare k1 k2 in
 			if (c != 0) then
 				c
 			else
 				Data.compare d1 d2
 	end
 	module Y = Set.make(X)
 	module Z = Map.make(Data)

 	type t = Y.t * (Key.t Z.t)

 	let empty : t = Y.empty, Z.empty

 	let add (s, m) k d =
 		try
 			let k' = Z.find d m in
 			let s = Y.remove (k', d) s in
 			let s = Y.add (k, d) s in
 			let m = Z.add d k m in
 			(s, m)
 		with
 		| Not_found ->
 			let s = Y.add (k, s) s in
 			let m = Z.add d k m in
 			(s, m)

 	let head (s, _) -> snd (Y.min_elt s)

end;;

All the other operations should be obvious.

Brian


>
> -- 
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] Priority queues

[Frédéric van der Plancke]

On 1/07/2011 10:32, Andrew wrote:
> Jean-Christophe Filliâtre wrote:
>>
>>> Are we talking about Dijkstra's graph traversal algorithm?
>>> If so, there is no need to increase/decrease anything.
>>
>> Implementing Dijkstra's shortest path algorithm actually requires to
>> decrease the priority of some nodes. But this does not mean your
>> priority queue data structure has to support such an operation.
>>
>> When you consider the edge x->y, x being the node you just extracted
>> from the priority queue, you might just have discovered a better path to
>> y and thus you have to update the priority associated to x. When there
>> is indeed such an improvement, you have two options:
>>
>> - either your priority queue data structure provides a decrease_key
>> operation, and then you use it; this is the case with Fibonacci heaps,
>> an imperative data structures which provides decrease_key in O(1) and
>> thus makes Dijkstra's algorithm complexity O(V log(V) + E).
>>
>> - or your priority queue does not provide such an operation, and you
>> simply add another entry for y in the priority queue, with a different
>> key. It means you have now several entries for y in the priority queue.
>> The better will be extracted first; the others will be ignored when they
>> are extracted later. Complexity is now O(E log(V)).
>
> Just an extra question though: How come it's not O(E log (E))? You 
> could end up pushing as much as one new element in your heap per edge, 
> couldn't you?
>

log(E) is O(log(V)), since log(E) <= 2 * log(V)...

Frédéric

Re: [Caml-list] Priority queues

[Andrew]

Jean-Christophe Filliâtre wrote:
>
>> Are we talking about Dijkstra's graph traversal algorithm?
>> If so, there is no need to increase/decrease anything.
>
> Implementing Dijkstra's shortest path algorithm actually requires to
> decrease the priority of some nodes. But this does not mean your
> priority queue data structure has to support such an operation.
>
> When you consider the edge x->y, x being the node you just extracted
> from the priority queue, you might just have discovered a better path to
> y and thus you have to update the priority associated to x. When there
> is indeed such an improvement, you have two options:
>
> - either your priority queue data structure provides a decrease_key
> operation, and then you use it; this is the case with Fibonacci heaps,
> an imperative data structures which provides decrease_key in O(1) and
> thus makes Dijkstra's algorithm complexity O(V log(V) + E).
>
> - or your priority queue does not provide such an operation, and you
> simply add another entry for y in the priority queue, with a different
> key. It means you have now several entries for y in the priority queue.
> The better will be extracted first; the others will be ignored when they
> are extracted later. Complexity is now O(E log(V)).

Just an extra question though: How come it's not O(E log (E))? You could end up pushing as much as one new element in 
your heap per edge, couldn't you?

Re: [Caml-list] Priority queues

[Andrew]

Wojciech Meyer wrote:
> Andrew<newsgroups.fr@gmail.com>  writes:
>
>> Wojciech Meyer wrote:
>>> And if one does not need performance but understanding what's the purpose of the priority queue is,
>>> what is the interface, and how it should behave, than implementation as a list is sufficient. Please note
>>> it is for exam and major pressure is put on Dijkstra not on implementation or performance (as far as I
>>> understood) of the priority queue. (which can be changed later easily)
>>
>> Not really. This is a practical exam. 3h and a half facing a computer,
>> with a set of problems to solve, with huge inputs. Hence the need for
>> performance.
>>
>> Here, Dijkstra's algorithm is only going to be a step in the process
>> of solving a more elaborate problem. Not having a priority queue
>> readily available means that I am going to have to waste some time
>> reimplementing an efficient structure.
>
> Yes, then you'd need a real priority queue.
>
> I would suggest using Batteries (some people might disagree and saying
> it's an overkill in this case). It all depends on the rules, if you can
> use any of code taken from home, or any external libraries for instance,
> or you would need to have them written down only on a piece of paper, or
> bringing some reference like book is feasible, etc. If it's all about
> high level problem solving, then they are ready algorithms for Dijkstra
> as well (e.g. excellent graph library: OCamlGraph).
>

I cannot import any code *at all* :/
>>
>> The Set option covers some cases (and it does work in the case of Dijkstra) ; but in other cases it won't work :/
>
> Yet it will work for Dijkstra, alternatively you could take some code
> out of standard OCaml library (Set, Map) and change it to your needs.
> (but I think that Redblack trees are easy enough to implement).
>
> Regarding your choice, I don't think you will regret OCaml even if it
> does not have the priority queue as a part of the standard library :)
> Like in the previous post, I also think it has some very nice features
> and also some ugly design features of C++ are not present in OCaml. I
> use to do a lot of C++ in past, and just feel much better now. (and
> features like fast GC, performance, pattern matching and many others
> just make programming so pleasant) It's worth investing time in O'Caml
> and certainly it's a perfect choice for this type of exam, (and really
> for any type of programming, I think).
>
> Mine two cents,
>
> Thanks,
> Wojciech
>
>

Re: [Caml-list] Priority queues

[Wojciech Meyer]

Andrew <newsgroups.fr@gmail.com> writes:

> Wojciech Meyer wrote:
>> And if one does not need performance but understanding what's the purpose of the priority queue is,
>> what is the interface, and how it should behave, than implementation as a list is sufficient. Please note
>> it is for exam and major pressure is put on Dijkstra not on implementation or performance (as far as I
>> understood) of the priority queue. (which can be changed later easily)
>
> Not really. This is a practical exam. 3h and a half facing a computer,
> with a set of problems to solve, with huge inputs. Hence the need for
> performance.
>
> Here, Dijkstra's algorithm is only going to be a step in the process
> of solving a more elaborate problem. Not having a priority queue
> readily available means that I am going to have to waste some time
> reimplementing an efficient structure.

Yes, then you'd need a real priority queue.

I would suggest using Batteries (some people might disagree and saying
it's an overkill in this case). It all depends on the rules, if you can
use any of code taken from home, or any external libraries for instance,
or you would need to have them written down only on a piece of paper, or
bringing some reference like book is feasible, etc. If it's all about
high level problem solving, then they are ready algorithms for Dijkstra
as well (e.g. excellent graph library: OCamlGraph).

>
> The Set option covers some cases (and it does work in the case of Dijkstra) ; but in other cases it won't work :/

Yet it will work for Dijkstra, alternatively you could take some code
out of standard OCaml library (Set, Map) and change it to your needs.
(but I think that Redblack trees are easy enough to implement).

Regarding your choice, I don't think you will regret OCaml even if it
does not have the priority queue as a part of the standard library :)
Like in the previous post, I also think it has some very nice features
and also some ugly design features of C++ are not present in OCaml. I
use to do a lot of C++ in past, and just feel much better now. (and
features like fast GC, performance, pattern matching and many others
just make programming so pleasant) It's worth investing time in O'Caml
and certainly it's a perfect choice for this type of exam, (and really
for any type of programming, I think).

Mine two cents,

Thanks,
Wojciech

Re: [Caml-list] Priority queues

[Christophe Raffalli]

[-- Attachment #1.1: Type: text/plain, Size: 1161 bytes --]

Hello again,

And by the way, for a competitive task in limited time, I would strongly
recommand
Strongly typed language with pattern-matching (I do not want to say
functionnal because it does no differentiate C from OCaml that much).

Look at ICFP result counting,

OCaml, ML, Haskell in the strongly typed with pattern matching class
C, C++ in the other class
Ignoring other languages (no time to sort them accurately)

After a quick count you get 15 agains 9 for appearance in the table at
http://en.wikipedia.org/wiki/ICFP_Programming_Contest

Clearly, you should also look at your current knowledge of each language ...

-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution 
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #1.2: Christophe_Raffalli.vcf --]
[-- Type: text/x-vcard, Size: 310 bytes --]

begin:vcard
fn:Christophe Raffalli
n:Raffalli;Christophe
org:LAMA (UMR 5127)
email;internet:christophe.raffalli@univ-savoie.fr
title;quoted-printable:Ma=C3=AEtre de conf=C3=A9rences
tel;work:+33 4 79 75 81 03
note:http://www.lama.univ-savoie.fr/~raffalli
x-mozilla-html:TRUE
version:2.1
end:vcard


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Caml-list] Priority queues

[Christophe Raffalli]

[-- Attachment #1.1.1: Type: text/plain, Size: 1304 bytes --]

Hello,
>
>
>     > Yes it does:
>     >
>     > http://caml.inria.fr/pub/docs/manual-ocaml/libref/Set.Make.html
>     >
>     > Please see min_elt function.
>     >
>
>     This is not an actual priority queue though: it doesn't allow for
>     multiple copies of the same element to be added :/
>
>
> Yes but you could simulate it with a list and map.
Or a set of tuple (p, id) where p is the priority and id the process
number (= arrival time).
Then you sort lexicographicaly first by increasing priority and second
decreasing id to have FIFO for equal priority.

And I think a less than 10 lines O(N ln(N)) re-implemantation or
priority queues would
give you good result at your competitive exam !
 
My two cents,
Christophe
>
> Cheers;
> Wojciech
>


-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution 
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #1.1.2: Type: text/html, Size: 2776 bytes --]

[-- Attachment #1.2: Christophe_Raffalli.vcf --]
[-- Type: text/x-vcard, Size: 310 bytes --]

begin:vcard
fn:Christophe Raffalli
n:Raffalli;Christophe
org:LAMA (UMR 5127)
email;internet:christophe.raffalli@univ-savoie.fr
title;quoted-printable:Ma=C3=AEtre de conf=C3=A9rences
tel;work:+33 4 79 75 81 03
note:http://www.lama.univ-savoie.fr/~raffalli
x-mozilla-html:TRUE
version:2.1
end:vcard


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 250 bytes --]

Re: [Caml-list] Priority queues

[Andrew]

Wojciech Meyer wrote:
 > And if one does not need performance but understanding what's the purpose of the priority queue is,
 > what is the interface, and how it should behave, than implementation as a list is sufficient. Please note
 > it is for exam and major pressure is put on Dijkstra not on implementation or performance (as far as I
 > understood) of the priority queue. (which can be changed later easily)

Not really. This is a practical exam. 3h and a half facing a computer, with a set of problems to solve, with huge 
inputs. Hence the need for performance.

Here, Dijkstra's algorithm is only going to be a step in the process of solving a more elaborate problem. Not having a 
priority queue readily available means that I am going to have to waste some time reimplementing an efficient structure.

The Set option covers some cases (and it does work in the case of Dijkstra) ; but in other cases it won't work :/

Re: [Caml-list] Priority queues

[Jean-Christophe Filliâtre]

> Are we talking about Dijkstra's graph traversal algorithm?
> If so, there is no need to increase/decrease anything.

Implementing Dijkstra's shortest path algorithm actually requires to
decrease the priority of some nodes. But this does not mean your
priority queue data structure has to support such an operation.

When you consider the edge x->y, x being the node you just extracted
from the priority queue, you might just have discovered a better path to
y and thus you have to update the priority associated to x. When there
is indeed such an improvement, you have two options:

- either your priority queue data structure provides a decrease_key
operation, and then you use it; this is the case with Fibonacci heaps,
an imperative data structures which provides decrease_key in O(1) and
thus makes Dijkstra's algorithm complexity O(V log(V) + E).

- or your priority queue does not provide such an operation, and you
simply add another entry for y in the priority queue, with a different
key. It means you have now several entries for y in the priority queue.
The better will be extracted first; the others will be ignored when they
are extracted later. Complexity is now O(E log(V)).

In practice, solution 2 in fast enough. This is what is implemented in
Ocamlgraph(using heaps I mentioned earlier).

See chapter 25 in the Cormen, for instance.

-- 
Jean-Christophe

Re: [Caml-list] Priority queues

[Wojciech Meyer]

[-- Attachment #1: Type: text/plain, Size: 986 bytes --]

On Thu, Jun 30, 2011 at 3:22 PM, David Rajchenbach-Teller <
David.Teller@ens-lyon.org> wrote:

> On 6/30/11 4:07 PM, Alexandre Pilkiewicz wrote:
>
>> I have the impression that none of the proposed solution allows to
>> increase/reduce the priority of an element, which is necessary for the
>> Dijkstra. (But I don't know any that does)
>>
>> - Alexandre
>>
> Are we talking about Dijkstra's graph traversal algorithm?
> If so, there is no need to increase/decrease anything.
>

Exactly, I think in that way as well. (in case if it's shortest path
problem).

And if one does not need performance but understanding what's the purpose of
the priority queue is,
what is the interface, and how it should behave, than implementation as a
list is sufficient. Please note
it is for exam and major pressure is put on Dijkstra not on implementation
or performance (as far as I
understood) of the priority queue. (which can be changed later easily)


> Best regards,
>  David
>

Cheers;
Wojciech

[-- Attachment #2: Type: text/html, Size: 1693 bytes --]

Re: [Caml-list] Priority queues

[David Rajchenbach-Teller]

On 6/30/11 4:07 PM, Alexandre Pilkiewicz wrote:
> I have the impression that none of the proposed solution allows to
> increase/reduce the priority of an element, which is necessary for the
> Dijkstra. (But I don't know any that does)
>
> - Alexandre
Are we talking about Dijkstra's graph traversal algorithm?
If so, there is no need to increase/decrease anything.

Best regards,
  David

Re: [Caml-list] Priority queues

[Michael Ekstrand]

On 06/30/2011 09:07 AM, Alexandre Pilkiewicz wrote:
> I have the impression that none of the proposed solution allows to
> increase/reduce the priority of an element, which is necessary for the
> Dijkstra. (But I don't know any that does)

Correct; none of them do, to my knowledge.  It's very rare that I've
actually seen a priority queue implementation that allows this (Java's
doesn't, for example).

- Michael

Re: [Caml-list] Priority queues

[Alexandre Pilkiewicz]

I have the impression that none of the proposed solution allows to
increase/reduce the priority of an element, which is necessary for the
Dijkstra. (But I don't know any that does)

- Alexandre

2011/6/30 Michael Ekstrand <michael@elehack.net>:
> On 06/30/2011 07:33 AM, Jean-Christophe Filliātre wrote:
>> I have an implementation of priority queues on my web page:
>>
>>   http://www.lri.fr/~filliatr/software.en.html
>>
>> Look for "heap". Note that it contains 2 implementations: one imperative
>> and one persistent. Help yourself
>
> I've used this heap implementation with good success.
>
> Batteries Included also contains a heap implementation (BatHeap) - if
> the OP is using Batteries, he can just use that heap as well.
>
> - Michael
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] Priority queues

[Michael Ekstrand]

On 06/30/2011 07:33 AM, Jean-Christophe Filliâtre wrote:
> I have an implementation of priority queues on my web page:
>
>   http://www.lri.fr/~filliatr/software.en.html
>
> Look for "heap". Note that it contains 2 implementations: one imperative
> and one persistent. Help yourself

I've used this heap implementation with good success.

Batteries Included also contains a heap implementation (BatHeap) - if
the OP is using Batteries, he can just use that heap as well.

- Michael

Re: [Caml-list] Priority queues

[Wojciech Meyer]

[-- Attachment #1: Type: text/plain, Size: 494 bytes --]

On Thu, Jun 30, 2011 at 1:34 PM, Andrew <newsgroups.fr@gmail.com> wrote:

> Wojciech Meyer wrote:
>
> > Yes it does:
> >
> > http://caml.inria.fr/pub/docs/**manual-ocaml/libref/Set.Make.**html<http://caml.inria.fr/pub/docs/manual-ocaml/libref/Set.Make.html>
> >
> > Please see min_elt function.
> >
>
> This is not an actual priority queue though: it doesn't allow for multiple
> copies of the same element to be added :/
>

Yes but you could simulate it with a list and map.

Cheers;
Wojciech

[-- Attachment #2: Type: text/html, Size: 906 bytes --]

Re: [Caml-list] Priority queues

[Andrew]

Wojciech Meyer wrote:

 > Yes it does:
 >
 > http://caml.inria.fr/pub/docs/manual-ocaml/libref/Set.Make.html
 >
 > Please see min_elt function.
 >

This is not an actual priority queue though: it doesn't allow for multiple copies of the same element to be added :/

Re: [Caml-list] Priority queues

[Jean-Christophe Filliâtre]

Hi,

> Does the standard library provide priority queues in OCaml? I'll be
> taking exams where I can use OCaml in a few days, but I couldn't find
> much documentation on priority queues online.

I have an implementation of priority queues on my web page:

  http://www.lri.fr/~filliatr/software.en.html

Look for "heap". Note that it contains 2 implementations: one imperative
and one persistent. Help yourself.

hope this helps,
-- 
Jean-Christophe

Re: [Caml-list] Priority queues

[Guillaume Yziquel]

Le Thursday 30 Jun 2011 à 13:56:19 (+0200), Andrew a écrit :
> Török Edwin wrote:
> >On 06/30/2011 02:30 PM, Andrew wrote:
> >>Hi there,
> >>
> >>Does the standard library provide priority queues in OCaml? I'll be taking exams where I can use OCaml in a few days, but I couldn't find much documentation on priority queues online.
> >>
> >
> >No, but the manual has an example of implementing priority queues:
> >http://caml.inria.fr/pub/docs/manual-ocaml/manual004.html
> 
> Ouch.
> 
> >>How would you implement Dijkstra's algorithm, otherwise?
> >
> >C doesn't have priority queues either (ok C++ does),
> >but you can implement them yourself.
> >
> 
> Perhaps I should have chosen C++ then. There's very little time in a
> competitive exam to implement fudamental data structures by
> yourself.

There's an implementation of them in Jane Street's library, and Markus
Mottl also has a repositorial where he implemented some structures from
Okasaki's little book.

	http://hg.ocaml.info/release/pure-fun/file/330eff97ead2

But I'm not sure whether that fits the scope of a "competitive exam".

-- 
     Guillaume Yziquel

Re: [Caml-list] Priority queues

[Wojciech Meyer]

[-- Attachment #1: Type: text/plain, Size: 906 bytes --]

On Thu, Jun 30, 2011 at 12:56 PM, Andrew <newsgroups.fr@gmail.com> wrote:

> Török Edwin wrote:
>
>> On 06/30/2011 02:30 PM, Andrew wrote:
>>
>>> Hi there,
>>>
>>> Does the standard library provide priority queues in OCaml? I'll be
>>> taking exams where I can use OCaml in a few days, but I couldn't find much
>>> documentation on priority queues online.
>>>
>>>
>> No, but the manual has an example of implementing priority queues:
>> http://caml.inria.fr/pub/docs/**manual-ocaml/manual004.html<http://caml.inria.fr/pub/docs/manual-ocaml/manual004.html>
>>
>
> Ouch.
>
>
>  How would you implement Dijkstra's algorithm, otherwise?
>>>
>>
>> C doesn't have priority queues either (ok C++ does),
>> but you can implement them yourself.
>>
>>
>
Yes it does:

http://caml.inria.fr/pub/docs/manual-ocaml/libref/Set.Make.html

Please see min_elt function.

Cheers;
Wojciech

[-- Attachment #2: Type: text/html, Size: 1970 bytes --]

Re: [Caml-list] Priority queues

[Andrew]

Török Edwin wrote:
> On 06/30/2011 02:30 PM, Andrew wrote:
>> Hi there,
>>
>> Does the standard library provide priority queues in OCaml? I'll be taking exams where I can use OCaml in a few days, but I couldn't find much documentation on priority queues online.
>>
>
> No, but the manual has an example of implementing priority queues:
> http://caml.inria.fr/pub/docs/manual-ocaml/manual004.html

Ouch.

>> How would you implement Dijkstra's algorithm, otherwise?
>
> C doesn't have priority queues either (ok C++ does),
> but you can implement them yourself.
>

Perhaps I should have chosen C++ then. There's very little time in a competitive exam to implement fudamental data 
structures by yourself.

Re: [Caml-list] Priority queues

[Török Edwin]

On 06/30/2011 02:30 PM, Andrew wrote:
> Hi there,
> 
> Does the standard library provide priority queues in OCaml? I'll be taking exams where I can use OCaml in a few days, but I couldn't find much documentation on priority queues online.
> 

No, but the manual has an example of implementing priority queues:
http://caml.inria.fr/pub/docs/manual-ocaml/manual004.html

> How would you implement Dijkstra's algorithm, otherwise?

C doesn't have priority queues either (ok C++ does),
but you can implement them yourself.

Best regards,
--Edwin

[Caml-list] Priority queues

[Andrew]

Hi there,

Does the standard library provide priority queues in OCaml? I'll be taking exams where I can use OCaml in a few days, 
but I couldn't find much documentation on priority queues online.

How would you implement Dijkstra's algorithm, otherwise?

Thanks!