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.
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 usar ninguno de los dos
Sección titulada «Cuándo NO usar ninguno de los dos»- 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).
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.