ejemplos - API de pila máxima incorporada en Python

django

Question

El heapq predeterminado es la implementación de la cola mínima y se pregunta si hay una opción para la cola máxima. Gracias.

Probé la solución utilizando _heapify_max para max heap, pero ¿cómo manejar el elemento push / pop dinámicamente? Parece que _heapify_max solo podría usarse durante el tiempo de inicialización.

import heapq
def heapsort(iterable):
h = []
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for i in range(len(h))]
if __name__ == "__main__":
print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

Editar, probar _heapify_max parece no funcionar para elementos dinámicos de inserción / pop. Intenté que ambos métodos produjeran el mismo resultado, ambos resultados son, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

def heapsort(iterable):
h = []
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for i in range(len(h))]
def heapsort2(iterable):
h = []
heapq._heapify_max(h)
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for i in range(len(h))]
if __name__ == "__main__":
print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print heapsort2([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

Gracias de antemano, Lin

Answer 1

En el pasado, simplemente he usado sortedcontainers de SortedList para esto, como:

> a = SortedList()
> a.add(3)
> a.add(2)
> a.add(1)
> a.pop()
3

No es un montón, pero es rápido y funciona directamente según sea necesario.

Si es absolutamente necesario que sea un montón, podría hacer una clase de negación general para guardar sus artículos.

class Neg():
def __init__(self, x):
self.x = x
def __cmp__(self, other):
return -cmp(self.x, other.x)
def maxheappush(heap, item):
heapq.heappush(heap, Neg(item))
def maxheappop(heap):
return heapq.heappop(heap).x

Pero eso será usar un poco más de memoria.

Answer 2

Hay una función _heappop_max en la última fuente de cpython que puede encontrar útil:

def _heappop_max(heap):
"""Maxheap version of a heappop."""
lastelt = heap.pop() # raises appropriate IndexError if heap is empty
if heap:
returnitem = heap[0]
heap[0] = lastelt
heapq._siftup_max(heap, 0)
return returnitem
return lastelt

Si cambia la lógica de heappush usando heapq._siftdown_max , debería obtener el resultado deseado:

def _heappush_max(heap, item):
heap.append(item)
heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
"""Maxheap version of a heappop."""
lastelt = heap.pop() # raises appropriate IndexError if heap is empty
if heap:
returnitem = heap[0]
heap[0] = lastelt
heapq._siftup_max(heap, 0)
return returnitem
return lastelt
def heapsort2(iterable):
h = []
heapq._heapify_max(h)
for value in iterable:
_heappush_max(h, value)
return [_heappop_max(h) for i in range(len(h))]

Salida:

In [14]: heapsort2([1,3,6,2,7,9,0,4,5,8])
Out[14]: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
In [15]: heapsort2([7, 8, 9, 6, 4, 2, 3, 5, 1, 0])
Out[15]: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
In [16]: heapsort2([19,13,15,17,11,10,14,20,18])
Out[16]: [20, 19, 18, 17, 15, 14, 13, 11, 10]
In [17]: heapsort2(["foo","bar","foobar","baz"])
Out[17]: [''foobar'', ''foo'', ''baz'', ''bar'']