El día 12/12/09, Pablo Mouzo <pablomouzo@???> escribió:
>
> 2009/12/12 Facundo Batista <facundobatista@???>:
> > 2009/12/12 Pablo Mouzo <pablomouzo@???>:
> >
> >> 2009/12/12 Facundo Batista <facundobatista@???>:
> >>>>>> import heapq
> >>>>>> heapq.nsmallest(2, [1, 4, 55, 65, 7, 3])
> >>> [1, 3]
> >>
> >> Crear un heap con n elementos no es O(n.log(n))?
> >
> > No sé.
> >
> > Habría que analizar el código del mismo.
> >
> > ¿Vos por qué decís que es O(n.log(n))?
> >
> > --
> > . Facundo
> >
>
>
> Si mal no recuerdo, al insertar un elemento nuevo en un heap, las
> operaciones necesarias para que vuelva a quedar con la propiedad del
> heap es log(n) (n es la cantidad de elementos que tiene el heap), y si
> tenés una lista de n elementos, con los cuales vas a crear un heap
> para sacar los más chicos, estás haciendo n veces el reordenamiento
> del heap. (Esta parte es la que no estoy seguro) Al final, cuando le
> sacas las constantes para llegar a la notacion big-O queda n.log(n).
>
> El heap es genial cuando queres mantener algo, a lo que le insertas y
> sacas elementos constantemente, ordenado. Por ejemplo una cola de
> mensajes con prioridad. Para todo lo demas existe quicksort :P.
>
> Saludos,
>
> Pablo
>
> ---------------------------------------------------------------------
> Para dar de baja la suscripcion, mande un mensaje a:
> pyar-unsubscribe@???
>
> Para obtener el resto de direcciones-comando, mande un mensaje a:
> pyar-help@???
>
> PyAr - Python Argentina - Sitio web: http://www.python.com.ar/
>
>
> Si N es la cantidad de cosas que tenes, n las que queres sacar:
El heap lo podes armar en O(N). Despues sacar el minimo te cuesta O(log(N)),
como vas a sacar n veces el minimo, lo que te queda es un O(n*log(N))
(text/plain)