API max heap integrata in Python

Question

L'heapq predefinito è l'implementazione della coda minima e si chiede se è disponibile un'opzione per la coda massima? Grazie.

Ho provato la soluzione utilizzando _heapify_max per l'heap massimo, ma come gestire l'elemento push/pop dinamico? Sembra che _heapify_max possa essere utilizzato solo durante il periodo di inizializzazione.

Modifica, provato _heapify_max sembra non funzionare per gli elementi push/pop dinamici. Ho provato entrambi i metodi in uscita allo stesso modo, entrambi i risultati sono, [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]) 

Grazie in anticipo, Lin

Answer 1

In passato ho usato semplicemente sortedcontainers s' SortedList per questo, come:

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

Non è un mucchio, ma è veloce e opere direttamente come richiesto.

Se è assolutamente necessario che sia un heap, è possibile creare una classe di negazione generale per contenere i propri articoli.

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 

Ma quello userà un po 'più di memoria.

Answer 2

C'è una funzione _heappop_max nell'ultima fonte CPython che si possono trovare utili:

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 

Se si modifica la logica heappush utilizzando heapq._siftdown_max si dovrebbe ottenere il risultato desiderato:

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

uscita :

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