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.