Saltearse al contenido

heapq y bisect

sorted() resuelve el 90 % de los problemas de orden. Los otros dos tienen nombre propio: quedarse con los k mejores y mantener una secuencia ordenada mientras se inserta. Para el primero hay un montículo; para el segundo, una búsqueda binaria. Y para ambos hay una forma ingenua que parece razonable y es entre 13 y 20 veces más lenta.

Un montículo no ordena: mantiene el mínimo accesible. bisect no ordena: encuentra dónde va.

Un heapq no es una clase, es un conjunto de funciones sobre una lista. La lista cumple una única invariante: el primer elemento es el menor. Nada más está ordenado.

import heapq
monton = [5, 1, 4, 2, 3]
heapq.heapify(monton) # [1, 2, 4, 5, 3] — sólo el primero está garantizado
heapq.heappush(monton, 0) # O(log n)
heapq.heappop(monton) # 0, O(log n)

Construir el montículo es O(n), no O(n log n): heapify reordena desde el centro hacia abajo. Insertar y extraer cuestan O(log n), que es lo que permite usarlo como cola de prioridad.

Los 10 mayores de un millón
sorted(...)[-10:] 187.9 ms heapq.nlargest(10) 14.3 ms

Trece veces. `nlargest` mantiene un montículo de tamaño k mientras recorre: O(n log k) en lugar de O(n log n).

Medido, no estimado
Operación Tiempo
sorted(datos)[-10:] 187.9 ms
heapq.nlargest(10, datos) 14.3 ms
heapq.heapify(datos) sobre 1M 22.6 ms

python mediciones/02-08-10-heap-registros-collections.py

La regla: en cuanto k es pequeño frente a n, nlargest/nsmallest ganan. Si necesitas el conjunto completo ordenado, sorted es lo correcto y no hay nada que optimizar.

import bisect
ordenada = [10, 20, 30, 40]
bisect.bisect_left(ordenada, 25) # 2 → el hueco
bisect.insort(ordenada, 25) # [10, 20, 25, 30, 40]

La búsqueda es O(log n) y cuesta 0,131 µs sobre una lista de 100 000. Insertar, en cambio, es O(n) porque mueve los punteros — el mismo problema del insert(0) del capítulo 02.

Y ahí está la sorpresa:

1 000 inserciones en una lista de 100 000
Estrategia Tiempo
bisect.insort una por una 12.80 ms
append y un sort() al final 0.66 ms

python mediciones/02-08-10-heap-registros-collections.py

Diecinueve veces peor. La búsqueda binaria es baratísima, pero cada inserción desplaza hasta 100 000 punteros. Acumular y ordenar una vez aprovecha Timsort: la lista ya está casi ordenada y el sort final es casi O(n).

insort gana cuando las inserciones están intercaladas con lecturas y la lista tiene que estar ordenada en todo momento. Si puedes acumular, acumula.

  • Si necesitas todo ordenado, sorted. El montículo no sirve para eso.
  • Si las inserciones son masivas y no hay lecturas intermedias, acumula y ordena al final.
  • Si necesitas búsqueda y también inserción frecuente, la estructura correcta no es una lista: es un árbol balanceado (sortedcontainers.SortedList) o un dict con índice.
  • Si n es pequeño, cualquiera de las tres opciones tarda microsegundos y la legibilidad decide.

Un sistema recibe 5 000 eventos por segundo y necesita, en todo momento, el evento más antiguo pendiente. ¿Montículo, bisect o lista ordenada? Razona el coste de cada uno.

Solución

Montículo, sin duda. La operación dominante es «sacar el mínimo» (heappop, O(log n)) y «añadir» (heappush, O(log n)). Con 5 000 eventos por segundo, la lista crece y decrece constantemente, y el montículo mantiene ambas operaciones logarítmicas.

bisect.insort sería O(n) por inserción por el desplazamiento: con una cola de 10 000 pendientes son 10 000 movimientos × 5 000 por segundo, inviable.

sorted() en cada consulta sería O(n log n) por evento: el peor de los tres.

El detalle de implementación: si los eventos pueden tener la misma marca de tiempo, la tupla (timestamp, evento) falla al comparar eventos. Añade un contador monótono como segundo campo: (timestamp, contador, evento).

  • Ramalho, L. Fluent Python, 2ª ed. Capítulo 2: bisect y heapq como alternativas a ordenar.
  • CPython 3.13: Modules/_heapqmodule.c, Modules/_bisectmodule.c.
  • Mediciones: mediciones/02-08-10-heap-registros-collections.py.
  • 07 · Ordenar sin ordenar de más: cuándo sorted es la respuesta.
  • 02 · list por dentro: por qué insort paga O(n).
  • 10 · collections: Counter.most_common usa internamente lo mismo que nlargest.