integrierte Max-Heap-API in Python

Question

Standard heapq ist min-Warteschlangenimplementierung und fragen, ob es eine Option für die maximale Warteschlange gibt? Vielen Dank.

Ich versuchte die Lösung mit _heapify_max für Max Heap, aber wie mit dynamisch Push/Pop-Element umgehen? Es scheint, dass _heapify_max nur während der Initialisierungszeit verwendet werden kann.

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

Bearbeiten, versuchte _heapify_max scheint nicht für dynamisch Push/Pop-Elemente zu arbeiten. Ich habe versucht beide Methoden gleich auszugeben, beide Ausgänge sind, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].

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

Es ist kein Haufen, aber es ist schnell und funktioniert:

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

Vielen Dank im Voraus, Lin

Answer 1

In der Vergangenheit habe ich einfach sortedcontainers ‚s SortedList dafür, wie gebraucht direkt nach Bedarf.

Wenn Sie es unbedingt als Heap benötigen, können Sie eine allgemeine Negationsklasse für Ihre Objekte erstellen.

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 

Aber das wird ein wenig mehr Speicher verwenden.

Answer 2

Es gibt eine _heappop_max Funktion in der neuesten CPython Quelle, die Sie nützlich finden können:

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 

Wenn Sie die heappush Logik ändern heapq._siftdown_max verwenden Sie die gewünschte Ausgabe erhalten sollte:

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

Ausgang :

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