API de stack máxima incorporada en Python

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 dynamics 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

    En el pasado, simplemente he usado SortedList 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 crear 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.

    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']