Hi, Not sure what I am going to say is relevant or not, but in my software GeneWeb, I implemented a priority queue a very simple way, and where insertion and get are in constant time.
But... my problem is very specific: my priorities are always integers between zero and a relatively small integer number (namely 100 or 150) and will very not likely become larger (and if it does, the queue can be easily dynamically extended). In that situation, my priority queue is just an array of that size (let's say 150) of lists of items. Insertion queue item = let p = item.priority in queue.(p) := item :: queue.(p) Get queue := let p = first_index_with_not_empty_list queue in let r = List.hd queue.(p) in queue.(p) := List.tl queue.(p); r -- Daniel de Rauglaudre http://pauillac.inria.fr/~ddr/ -- 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
