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=1.2 required=5.0 tests=AWL,SPF_SOFTFAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 54411BB84 for ; Mon, 12 Jan 2009 11:22:33 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArEDAJqoaknAI/YUgWdsb2JhbACBbJIlAQEWIr1uhW8 X-IronPort-AV: E=Sophos;i="4.37,252,1231110000"; d="scan'208";a="33605742" Received: from ns2.inescn.pt (HELO trubo.inescn.pt) ([192.35.246.20]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 12 Jan 2009 11:22:33 +0100 Received: from localhost (localhost [127.0.0.1]) by trubo.inescn.pt (8.13.8/8.13.8/8) with ESMTP id n0CAMVe1024502 for ; Mon, 12 Jan 2009 10:22:31 GMT X-Virus-Scanned: amavisd-new at inescporto.pt Received: from trubo.inescn.pt ([127.0.0.1]) by localhost (trubo.inescn.pt [127.0.0.1]) (amavisd-new, port 10024) with LMTP id CEIIbONr3c93 for ; Mon, 12 Jan 2009 10:22:18 +0000 (WET) Received: from grover.inescn.pt (grover.inescn.pt [194.117.24.20]) by trubo.inescn.pt (8.13.8/8.13.8/56) with ESMTP id n0CAM5Kr024469 for ; Mon, 12 Jan 2009 10:22:05 GMT Received: from [194.117.30.117] (merlinix.inescn.pt [194.117.30.117]) by grover.inescn.pt (8.13.8/8.13.8/5) with ESMTP id n0CAM4jW028304 for ; Mon, 12 Jan 2009 10:22:05 GMT Message-ID: <496B19CA.5060703@inescporto.pt> Date: Mon, 12 Jan 2009 10:22:02 +0000 From: Hugo Ferreira User-Agent: Thunderbird 2.0.0.19 (X11/20090105) MIME-Version: 1.0 To: caml-list@yquem.inria.fr Subject: Heap implementations: Fibonacci, Brodal and relaxed Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; haskell:01 wikipedia:01 wiki:01 heap:01 heap:01 functional:02 aka:04 aka:04 max:06 tia:08 comments:10 heaps:10 heaps:10 fibonacci:13 fibonacci:13 Hello, I would like to now if anyone has or knows of functional implementations of priority (aka Min, aka Max) heaps. Specifically I am looking for: Fibonacci, Brodal and relaxed heaps [1] with fast insert and deletes. Any literature or implementation in Haskell or F# are also welcome. I also would appreciate any additional comments on implementation issues and experience with heaps that may help me. TIA, Hugo Ferreira. [1] http://en.wikipedia.org/wiki/Fibonacci_heap