Kann Pythons Heapify() nicht gut mit Listenverständnis und Slicing spielen?

Question

Ich fand einen interessanten Fehler in einem Programm, das ich etwas träge implementierte, und fragte mich, ob ich es richtig verstehe. Die kurze Version ist, dass Python's heapq implementation nicht wirklich eine Liste bestellt, sondern lediglich die Liste auf eine Heap-zentrierte Weise gruppiert. Insbesondere erwartete ich, dass heapify() zu einer geordneten Liste führte, die das Listenverständnis in geordneter Weise erleichterte.

eine Priorität Stichwort Beispiel verwenden, wie in der Python-Dokumentation:

from heapq import heapify, heappush, heappop 
from random import shuffle 

class Item(object): 
    def __init__(self, name): 
     self.name = name 

lst = [] 

# iterate over a pseudo-random list of unique numbers 
for i in sample(range(100), 15): 
    it = Item("Some name for %i" % i) 
    heappush(lst, (i, it)) 

print([i[0] for i in lst]) 

Ergebnisse in

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67] 

Diese stellen wir fest, ist nicht die Original Reihenfolge der Liste, aber anscheinend einige Heap-zentrische Reihenfolge wie . Ich habe träge erwartet, dass dies vollständig bestellt wird.

Als Test die Liste durch heapify läuft() führt zu keiner Veränderung (wie die Liste bereits heap-ishly bestellt ist):

heapify(lst) 

print([i[0] for i in lst]) 

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67] 

Während bei den heappop() Funktion Ergebnisse bei der Bestellung durch die Liste iterieren wie erwartet:

lst2 = [] 
while lst: lst2.append(heappop(lst)) 

print([i[0] for i in lst2]) 

>>> [2, 7, 10, 22, 27, 32, 33, 40, 45, 51, 67, 69, 89, 94, 97] 

so würde es scheinen, dass heapq keine Liste nicht bestellt werden (zumindest im menschlichen Sinne des Wortes), sondern die heappush() und heappop() Funktionen sind in der Lage grok die heap-ishly geordnete Liste.

Das Ergebnis: Alle Operationen zum Schneiden und Listenverstehen in einer Liste führen zu nicht geordneten Ergebnissen.

Ist das wahr, und ist das immer wahr?

(BTW: Python 3.0.1 auf einem WinXP System)

Answer 1

Ein Heap ist nicht eine sortierte Liste (es ist eine Darstellung eines teilweise sortierten Binärbaum).

Also ja, Sie haben recht, wenn Sie erwarten, dass sich eine heapifizierte Liste wie eine sortierte Liste verhält, werden Sie enttäuscht sein. Die einzige Sortierannahme, die Sie für einen Heap vornehmen können, ist, dass heap[0] immer das kleinste Element ist.

(. Es ist schwierig, viel hinzuzufügen, was Sie bereits geschrieben haben - Ihre Frage ist eine ausgezeichnete Zuschreibung von, wie die Dinge 8-)

Answer 2

Das Ergebnis: Jedes Aufschneiden und Liste Verständnis Operationen auf ein Heap-Liste führt zu nicht geordneten Ergebnissen.

Ist das wahr, und ist das immer wahr?

Wenn Sie nur eine einmalige sortierte Liste zu erhalten, verwenden Sie:

myList.sort() 

Priority Queues/Heaps kann eine Art zu implementieren, verwendet werden, oder sie können verwendet werden, um eine Warteschlange zu halten Prioritätsform. Einfügungen in einen Heap sind O (lg n), gets sind O (1) und Entfernungen sind O (lg n), was viel besser ist, als die gesamte Liste immer wieder neu zu sortieren.

Answer 3

"" "Ich habe erwartet, dass haufig() zu einer geordneten Liste führt, die das Listenverstehen in geordneter Weise erleichtert." "": Wenn diese Erwartung auf dem Lesen des Handbuchs beruht, sollten Sie einen Dokumentfehler melden Bericht.

"" "Das Ergebnis: Jegliches Schneiden und Listenverstehen Operationen auf einer zusammenhängenden Liste wird ungeordnete Ergebnisse liefern. Ist das wahr, und ist das immer wahr?" "": Genau wie z.B. random.shuffle(), die angegebene Aktivität ist nicht definiert, um "geordnete" Ergebnisse zu erzeugen. Es Mai produzieren gelegentlich "bestellt" Ergebnisse, aber das ist zufällig und nicht verlässlich und nicht wert, zu fragen (IMHO).

Answer 4

"Das Ergebnis: Jegliches Schneiden und Listenverständnis Operationen auf einer Liste werden nicht-geordnete Ergebnisse ergeben. Ist das wahr, und ist das immer wahr?" Nein, es ist nicht immer wahr. Obwohl es die meiste Zeit nicht bestellt ist, kann es bestellt werden. heapify() erzeugt eine Liste, die die "Heap-Invariante" erfüllt. In diesem Fall handelt es sich um einen Min-Heap. Es stellt sich heraus, dass eine sortierte Liste auch die Heap-Invariante erfüllt (siehe heapq Absatz 4: "heap.sort() verwaltet die Heap-Invariante"). Theoretisch ist es also möglich, dass eine zusammengesetzte Liste zufällig sortiert wird.