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.0 required=5.0 tests=AWL,SPF_NEUTRAL 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 E3013BC69 for ; Fri, 20 Jul 2007 15:34:12 +0200 (CEST) Received: from wx-out-0506.google.com (wx-out-0506.google.com [66.249.82.226]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6KDYBoR028210 for ; Fri, 20 Jul 2007 15:34:12 +0200 Received: by wx-out-0506.google.com with SMTP id h28so836585wxd for ; Fri, 20 Jul 2007 06:34:11 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=uOGv+H7c7gvtpqCM5/5dGe5X/zLS4ASX0kCsLbb/D9o3itCu+UZkDc7jL3is+3/layzAqwo3lpuONt1NfHF/QXfQPzEMtJmqcrL+t0T/7U8H+YJfS0Ot/DXhsg2rw6ugHU8laiJYKDC4qDXquWXz5dW88aLIzcGxhuHPqo1c4yo= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=fiftVJQPA6AHIXQMxmT4l1gmGBMjVDWrAerTLH9podSg12JOxtaVqd4yXz/BcbWr4KNoP71SCp5k3w85Ml+2yfgSDdgD95rIP1ccIZ9c2Nz7JhP+REfCDrGtit/zSxp7tb0G8ryxgoS9en7Nej+zDY1aKd2qM0mJJYxAG+efkGo= Received: by 10.90.113.20 with SMTP id l20mr287601agc.1184938451021; Fri, 20 Jul 2007 06:34:11 -0700 (PDT) Received: by 10.90.71.11 with HTTP; Fri, 20 Jul 2007 06:34:10 -0700 (PDT) Message-ID: <6dbd4d000707200634l20f4e61fyc7051804b608677e@mail.gmail.com> Date: Fri, 20 Jul 2007 07:34:10 -0600 From: "Denis Bueno" To: "OCaml Mailing List" Subject: Announcement: fiblib 0.1, a fibonacci heap library MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline X-j-chkmail-Score: MSGID : 46A0B9D3.001 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at discorde with ID 46A0B9D3.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 pseudocode:01 heap:01 heap:01 imperative:01 data:02 algorithms:03 library:03 library:03 let:03 structure:07 efficient:07 release:09 release:09 i'm:09 Dear OCaml hackers, I'm pleased to announce the first release of fiblib, an efficient, imperative Fibonacci heap library, based on the pseudocode of Cormen, Leiserson, Rivest, and Stein: http://code.google.com/p/fiblib/ This implementation provides a base of operations you'd expect from a heap (with more to come): - insert - extract min - delete - decrease key Other operations, such as union, are slated for another release. Though a relatively obscure data structure, they are the best known solution for certain algorithms requiring a heap. In particular, a fibonacci heap is a win if the number of extract-min and delete operations is small compared to the number of other operations. Fiblib is released under a BSD-style license, so, if you need a heap, try it out, and let me know how it goes! -- Denis