Binärer Heap
Verfasst: Sonntag 22. Juli 2018, 16:40
Hallo
Das ist eine etwas umfangreichere Einführung mit zwei Fragen am Schluss. Ich brauche für ein Python-Programm einen binärer Heap. Ich habe Objekte, denen jeweils ein Wert zugeordnet ist und ich möchte so ein Ojekt in den Heap einfügen:
das Objekt mit dem kleinsten Wert aus der heraus lesen und entfernen:
und manchmal ändert sich der Wert eines Objekts, er wird kleiner. Dann muss das im Heap angepasst werden:
In Python gibt es “heapq — Heap queue algorithm”, das das im wesentlichen implementiert.
entspricht der Funktion extractMin und
entspricht der Prozedur insert des binären Heap. Es kann für ‘Item’ das Paar ‘(key, obj)’ verwendet werden. Der Heap ist dabei einfach eine Liste, die durch ‘heappop’ und ‘heappush’ geeignet verwaltet wird. Das heißt, das Programm startet mit
und danach werden mit heappush items hinzugefügt bzw. mit heappop wieder entfernt.
Für die Elemente der Liste gilt immer
und damit it heap[0] das kleinste Element.
Die Prozedur ‘decreaseKey(binaryheap, obj, new_key)’ kann nun folgendermaßen implementiert werden, wenn i der Index von obj in der List ‘binaryheap’ ist:
Allerdings ist dazu die Kenntnis des Indexes i des Objekts in der Liste nötig, und den weiß ich aber nicht. Natürlich könnte ich heappush und heappop selbbst implementieren aber das ist dann vermutlich langsamer. Gibt es eine Möglichkeit heapq zu verwenden?
Ich denke zum Beispiel, dass man aus der list-Klasse eine neue Klasse ableitet und die entsprechenden Methoden, die das Einfügen von Elementen in die Liste durchführen, geeignet überschreibt, sodass sie ein Dictionary mitpflegen, das für jedes Objekt in der Liste den dazugehörenden Listenindex enthält.
Meine Fragen:
Das ist eine etwas umfangreichere Einführung mit zwei Fragen am Schluss. Ich brauche für ein Python-Programm einen binärer Heap. Ich habe Objekte, denen jeweils ein Wert zugeordnet ist und ich möchte so ein Ojekt in den Heap einfügen:
Code: Alles auswählen
insert(binaryheap,obj,key)
Code: Alles auswählen
(obj,key)=extractMin(binaryheap)
Code: Alles auswählen
decreaseKey(binaryheap, obj, new_key)
Code: Alles auswählen
heapq.heappop(binaryheap)
Code: Alles auswählen
heapq.heappush(binaryheap, item)
Code: Alles auswählen
binaryheap=[]
Für die Elemente der Liste gilt immer
Code: Alles auswählen
binaryheap[k] <= binaryheap[2*k+1]
und
binaryheap[k] <= binaryheap[2*k+2]
Die Prozedur ‘decreaseKey(binaryheap, obj, new_key)’ kann nun folgendermaßen implementiert werden, wenn i der Index von obj in der List ‘binaryheap’ ist:
Code: Alles auswählen
while i>0 and binaryheap[i]<binaryheap[(i-1)//2]:
(binaryheap[i],binaryheap[(i-1)//2])=(binaryheap[(i-1)//2]<binaryheap[i])
i=(i-1)//2
Ich denke zum Beispiel, dass man aus der list-Klasse eine neue Klasse ableitet und die entsprechenden Methoden, die das Einfügen von Elementen in die Liste durchführen, geeignet überschreibt, sodass sie ein Dictionary mitpflegen, das für jedes Objekt in der Liste den dazugehörenden Listenindex enthält.
Meine Fragen:
- Ist das möglich einen binären Heap mit Hilfe von heapq zu implementieren und wenn ja, wie? Welche Methode muss isch überschreiben?
- Ist das sinnvoll? Wenn ich jedesmal, wenn ein Listenelement den Platz wechselt, die Prozedur zum Pflegen des Dictionary-Objekts aufrufen muss, dann bin ich vielleicht sowieso schon so langsam, dass ich gleich alles selbst in Python neu implementieren kann, ohne heapq zu verwenden.