Binärer Heap

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
miracle173
User
Beiträge: 127
Registriert: Samstag 6. Februar 2016, 00:28

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:

Code: Alles auswählen

insert(binaryheap,obj,key)
das Objekt mit dem kleinsten Wert aus der heraus lesen und entfernen:

Code: Alles auswählen

(obj,key)=extractMin(binaryheap)
und manchmal ändert sich der Wert eines Objekts, er wird kleiner. Dann muss das im Heap angepasst werden:

Code: Alles auswählen

decreaseKey(binaryheap, obj, new_key)
In Python gibt es “heapq — Heap queue algorithm”, das das im wesentlichen implementiert.

Code: Alles auswählen

heapq.heappop(binaryheap)
entspricht der Funktion extractMin und

Code: Alles auswählen

heapq.heappush(binaryheap, item)
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

Code: Alles auswählen

binaryheap=[]
und danach werden mit heappush items hinzugefügt bzw. mit heappop wieder entfernt.

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

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
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:
  1. Ist das möglich einen binären Heap mit Hilfe von heapq zu implementieren und wenn ja, wie? Welche Methode muss isch überschreiben?
  2. 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.
mfg miracle173
Antworten