From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id BF12BBC6B for ; Sat, 4 Aug 2007 14:25:41 +0200 (CEST) Received: from bsd4.nyct.net (mail-out8.nyct.net [216.139.141.8]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l74CPe07020432 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sat, 4 Aug 2007 14:25:41 +0200 Received: from [192.168.42.2] (adsl-216-139-154-52.nyct.net [216.139.154.52]) by bsd4.nyct.net (8.13.4/8.13.4) with ESMTP id l74CPVJ0000398; Sat, 4 Aug 2007 08:25:32 -0400 (EDT) (envelope-from bhurt@spnz.org) Date: Sat, 4 Aug 2007 08:36:18 -0400 (EDT) From: Brian Hurt X-X-Sender: bhurt@localhost To: tmp123@menta.net Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Sorted list In-Reply-To: Message-ID: References: <46B4485B.7040406@menta.net> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at discorde with ID 46B47044.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; node:01 mutable:01 pointer:01 node:01 heap:01 caml-list:01 arbitrary:02 purely:02 data:02 functional:02 element:03 element:03 brian:05 brian:05 comparison:05 I forgot a bit of analysis as to why I recommend that data structure, and not others. The advantage a priority queue has is that peeking at the head node (highest priority) element is O(1), and in this case very fast. This is in comparison with the O(log N) cost of using a map or tree-based list. I was assuming that since you were implementing a timer queue, the bulk of the accesses will be "has the next timer timed out yet? No- moving on..." You can implement a mutable version of the leftist heap, and keep a parent pointer in the node. This allows you to remove an arbitrary node in O(log N) time, during the delete function (as opposed to waiting for the timer to time out to remove it). But it's a lot more complicated- the idea is easier to see in the purely functional code. If you want to use a map, have each element be a list of timers set to expire at the same time. Brian