From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p5UI3E0A021481 for ; Thu, 30 Jun 2011 20:03:14 +0200 X-IronPort-AV: E=Sophos;i="4.65,453,1304287200"; d="scan'208";a="97749855" Received: from yquem.inria.fr ([128.93.8.37]) by mail2-relais-roc.national.inria.fr with ESMTP; 30 Jun 2011 20:03:09 +0200 Received: by yquem.inria.fr (Postfix, from userid 25991) id AE9F4E1BC7; Thu, 30 Jun 2011 20:03:09 +0200 (CEST) Date: Thu, 30 Jun 2011 20:03:09 +0200 From: Daniel de Rauglaudre To: caml-list@inria.fr Message-ID: <20110630180309.GA11388@yquem.inria.fr> References: <848371343.3424870.1309454037170.JavaMail.root@zmbs3.inria.fr> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: <848371343.3424870.1309454037170.JavaMail.root@zmbs3.inria.fr> User-Agent: Mutt/1.5.18 (2008-05-17) Subject: Re: [Caml-list] Priority queues, reloaded 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/