heapq y bisect
sorted() resuelve casi todos 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.
En una línea
Sección titulada «En una línea»Un montículo no ordena: mantiene el mínimo accesible. bisect no ordena: encuentra dónde va.
El montículo: orden parcial y barato
Sección titulada «El montículo: orden parcial y barato»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á garantizadoheapq.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 k mayores
Sección titulada «Los k mayores»Trece veces. `nlargest` mantiene un montículo de tamaño k mientras recorre: O(n log k) en lugar de O(n log n).
| 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.
bisect: encontrar el hueco
Sección titulada «bisect: encontrar el hueco»import bisect
ordenada = [10, 20, 30, 40]bisect.bisect_left(ordenada, 25) # 2 → el huecobisect.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:
| 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.
La trampa
Sección titulada «La trampa»Cuándo no aplica
Sección titulada «Cuándo no aplica»- 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 undictcon índice. - Si
nes pequeño, cualquiera de las tres opciones tarda microsegundos y la legibilidad decide.
Ejercicio
Sección titulada «Ejercicio»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).
Comprobación del desempate con el contador monótono:
import heapqfrom itertools import count
contador = count()cola = []for marca, evento in [(5, {"id": "b"}), (5, {"id": "a"}), (3, {"id": "c"})]: heapq.heappush(cola, (marca, next(contador), evento))
orden = [heapq.heappop(cola)[2]["id"] for _ in range(3)]print("orden de salida:", orden)
try: heap_sin_contador = [(5, {"id": "x"})] heapq.heappush(heap_sin_contador, (5, {"id": "y"}))except TypeError as error: print("sin contador:", type(error).__name__)Referencias
Sección titulada «Referencias»- Ramalho, L. Fluent Python, 2ª ed. Capítulo 2:
bisectyheapqcomo alternativas a ordenar. - CPython 3.13:
Modules/_heapqmodule.c,Modules/_bisectmodule.c. - Mediciones:
mediciones/02-08-10-heap-registros-collections.py.
Capítulos relacionados
Sección titulada «Capítulos relacionados»- 07 · Ordenar sin ordenar de más: cuándo
sortedes la respuesta. - 02 ·
listpor dentro: por quéinsortpaga O(n). - 10 ·
collections:Counter.most_commonusa internamente lo mismo quenlargest.