Ich habe diese Lösung auf eine Frage unter leetcode.com überprüft

def topKFrequent(self, words, k):
        count = collections.Counter(words)
        heap = [(-freq, word) for word, freq in count.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in xrange(k)]

Und wenn ich ihm ein Array von Zeichenfolgen wie ["aa", "aaa", "a"] und 1 zur Verfügung stelle, gibt es ["a"] korrekt zurück. Meine Frage ist, hat der Haufen die Tupel auch lexographisch intern sortiert? Denn wenn es keine Sortierung gegeben hätte, hätte es einfach ["aa"] zurückgegeben (die Reihenfolge, in der der Heap erstellt wurde, da die Anzahl aller drei gleich ist). Oder habe ich heapq falsch verstanden?

1
Saturnian 19 Feb. 2020 im 20:03

3 Antworten

Beste Antwort

heapq vergleicht nur Werte aus der Warteschlange mit dem Operator "kleiner als" [1] , unabhängig vom Typ des Werts. Es ist der Typ des Werts, der definiert, was der Vergleich zurückgibt. Shat macht also den Unterschied, hier ist das Tupel selbst. Ab der Dokumentation:

Der Vergleich [von Sequenzobjekten] verwendet eine lexikografische Reihenfolge: Zuerst werden die ersten beiden Elemente verglichen, und wenn sie sich unterscheiden, bestimmt dies das Ergebnis des Vergleichs; Wenn sie gleich sind, werden die nächsten beiden Elemente verglichen usw., bis eine der beiden Sequenzen erschöpft ist.

Überprüfen Sie einige Beispiele:

>>> (0, 'a') < (1, 'aa')
True
>>> (1, 'a') < (1, 'aa')
True
>>> (1, 'aa') < (1, 'a')
False
>>> (2, 'a') < (1, 'aa')
False

Sie haben also Recht, die Werte sind lexikografisch geordnet und der zweite Wert des Tupels ist relevant. heapq muss hier jedoch nichts tun, um dieses Ergebnis zu erhalten. Der bloße Tupelvergleich macht dies.

[1] Man kann es im Code überprüfen. Hier ist eine der Zeilen, in denen der Vergleich erfolgt erstellt von heapq (in C):

cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);

Dieses PyObject_RichCompareBool() ist laut der Dokumentation:

das Äquivalent des Python-Ausdrucks o1 op o2, wobei op der Operator ist, der opid entspricht.

1
brandizzi 19 Feb. 2020 im 17:40

Haufen sind Teilbestellungen. Sie sind nicht sortiert. Sie können jedoch Sortierungen daraus erstellen, indem Sie Werte in einem Heap speichern und einzeln herausziehen. Diese Sortierungen sind nicht stabil, da Heaps nicht versuchen, die Reihenfolge "gleicher" Werte beizubehalten.

Hier ist eine andere Art von Python-Heap, an der Sie interessiert sein könnten: https://pypi.org/project/fibonacci-heap-mod/

0
dstromberg 19 Feb. 2020 im 17:14

Sie haben einen Haufen von Ganzzahl / Zeichenfolge-Paaren, und daher wird er anhand der Definition von < für Tupel sortiert, wobei beide Elemente jedes Typs berücksichtigt werden.

Bei ["aa", "aaa", "a"] ist count.items() eine Folge von Tupeln [('aa', 1), ('aaa', 1), ('a', 1)]. Anschließend erstellen Sie mithilfe der Tupelliste einen Heap

[(-1, 'aa'), (-1, 'aaa'), (-1, 'a')]

Da das erste Element jedes Tupels dasselbe ist, werden die Vergleiche ausschließlich durch das zweite String-Element bestimmt.

3
chepner 19 Feb. 2020 im 17:14