Re: [Caml-list] Priority queues, reloaded

[Daniel de Rauglaudre <daniel.de_rauglaudre@inria.fr>]

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/