From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p61Mb7Uf019544
	for <caml-list@sympa-roc.inria.fr>; Sat, 2 Jul 2011 00:37:07 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AoUDAIJKDk7RVaG+i2dsb2JhbABSmQ6OawgUAQEBCgsLBxIGIa19jCSGZzmIbYYyBIc+g2GTMTyDdw
X-IronPort-AV: E=Sophos;i="4.65,460,1304287200"; 
   d="scan'208";a="112367292"
Received: from mail-gx0-f190.google.com ([209.85.161.190])
  by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Jul 2011 00:37:02 +0200
Received: by gxk7 with SMTP id 7so3116806gxk.27
        for <caml-list@inria.fr>; Fri, 01 Jul 2011 15:37:01 -0700 (PDT)
Received: by 10.91.164.3 with SMTP id r3mr437070ago.5.1309559821194; Fri, 01
 Jul 2011 15:37:01 -0700 (PDT)
Path: glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: fa.caml
Date: Fri, 1 Jul 2011 15:37:01 -0700 (PDT)
In-Reply-To: <fa.zXwbS6BNVmuh5Yg3lR+NAiHb7b8@ifi.uio.no>
Reply-To: fa.caml@googlegroups.com
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=188.221.185.251;
 posting-account=e5mzsQoAAAB7g9y7Bkgam0zJDHRr7bCB
NNTP-Posting-Host: 188.221.185.251
User-Agent: G2/1.0
X-Google-Web-Client: true
MIME-Version: 1.0
Message-ID: <0bb28c99-9ffd-4b5d-b073-8aff7af00493@glegroupsg2000goo.googlegroups.com>
From: Radu Grigore <radugrigore@gmail.com>
To: fa.caml@googlegroups.com
Cc: caml-list@inria.fr, Jean-Christophe.Filliatre@lri.fr
Content-Type: text/plain; charset=ISO-8859-1
Subject: Re: [Caml-list] Priority queues

On Friday, July 1, 2011 11:33:11 AM UTC+1, Andrew wrote:
> > - or your priority queue does not provide such an operation, and you
> > simply add another entry for y in the priority queue, with a different
> > key. It means you have now several entries for y in the priority queue.
> > The better will be extracted first; the others will be ignored when they
> > are extracted later. Complexity is now O(E log(V)).
> 
> Just an extra question though: How come it's not O(E log (E))?
> You could end up pushing as much as one new element in 
> your heap per edge, couldn't you?

If you use a Set of (distance, vertex) pairs together with min_elt then you can simulate decrease-key using remove followed by add.