Soru Python'da yerleşik maksimum yığın API'si


Varsayılan heapq min kuyruk uygulaması ve maksimum kuyruk için bir seçenek olup olmadığını merak ediyor? Teşekkürler.

Maxheap için _heapify_max kullanarak çözümü denedim, ancak dinamik olarak push / pop elemanını nasıl kullanacağım? _Heapify_max sadece başlatma zamanı sırasında kullanılabilir.

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

Düzenleme, denedim _heapify_max dinamik olarak itme / pop öğeleri için çalışmıyor görünüyor. Her iki yöntem de aynı çıktıyı denedim, her iki çıktı da [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])

Şimdiden teşekkürler, Lin


18
2017-10-08 19:19


Menşei


Olası kopya Python'da maksimum yığın uygulaması için ne kullanırım? - Lukas Graf
@LukasGraf, arama fonksiyonu olup olmadığından emin değilim heapify_max iyi, çünkü önek görüyorum "", dahili bir işlev gibi görünüyor? - Lin Ma
@ LukasGraf, ilk çözüm beni tam olarak uymuyor çünkü hem tamsayı hem de dizgileri ele almam gerekiyor. :) - Lin Ma
Evet, buradaki durum gerçekten tatmin edici değil. Hala, soru Gibi tam olarak bir çoğaltma olduğunu. Ancak bulabilirsin bu cevap faydalı. - Lukas Graf
_heapify_max, girişinizi maksimum bir yığına dönüştürecektir. Ancak, heappop ve heappush hala minik yığın tabanlı. Heapq modülünün kaynak kodunu buradan kontrol edebilirsiniz: github.com/python/cpython/blob/master/Lib/heapq.py Aslında alabileceğiniz bir _heappop_max işlevi vardır, bu da maksimum yığında kullanılmalıdır. _Heappush_max yok. Ama bir tane yazmak için heappush işlevini kolayca değiştirebilirsiniz. Veya sürümümü buradan kontrol edin: github.com/he-zhe/heapq_max/blob/master/heapq_max/... - Zhe He


Cevaplar:


Geçmişte basitçe kullandım sortedcontainers'ler SortedList bunun için, şöyle:

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

Bu bir yığın değil, ama hızlı ve gerektiği gibi doğrudan çalışır.

Bir yığına kesinlikle ihtiyacınız varsa, eşyalarınızı tutmak için genel bir olumsuzlama sınıfı yapabilirsiniz.

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

Ama bu biraz daha fazla bellek kullanıyor olacak.


21
2017-10-11 07:14



İyi yakalama. Çözümünüzün sayısal türlerin yanı sıra dize için çalışıp çalışmadığını mı merak ediyorsunuz? - Lin Ma
@LinMa Bu, sarıcının işi bu. Verilerinizin sayısal olduğunu biliyorsanız, yalnızca kullanarak biraz daha iyi yapabilirsiniz. - de olduğu gibi def maxheappush(heap, item): heapq.heappush(heap, -item) ve def maxheappop(heap): return -heapq.heappop(heap). - U2EF1
Teşekkürler U2EF1, nasıl ve ne zaman cmp çağrıldı ve kaldıraçlı? - Lin Ma
@ LinaMa Evet, gibi işlemler a < b üzerinde Neg örnekler arayacak __cmp__. Arandığını görmek istiyorsanız, bazı baskı ifadeleri ekleyebilirsiniz. - U2EF1
@anveshtummala Endeksleme ile ala a[-1]. - U2EF1


Var _heappop_max yararlı bulabileceğiniz en son cpython kaynağındaki işlev:

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

Değiştirirseniz heappush kullanarak mantık heapq._siftdown_max İstediğiniz çıktıyı almalısınız:

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

Çıktı:

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

4
2017-10-11 23:26



Merhaba Padraic, sadece Python 3 için çalışıyor? - Lin Ma
Merhaba Lin, benim için 2 ve 3 için çalışıyor - Padraic Cunningham