eine binäre Heap-Implementierung gibt falsches Ergebnis zu schaffen

Question

mir den binären Heap nach einem Online-Kurs Implementierung und ich habe folgend getan:

from __future__ import division 

class BinaryHeap(object): 
    def __init__(self, arr=None): 
     self.heap = [] 

    def insert(self, item): 
     self.heap.append(item) 
     self.__swim(len(self.heap) - 1) 

    def __swim(self, index): 
     parent_index = (index - 1) // 2 
     while index > 0 and self.heap[parent_index] < self.heap[index]: 
      self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index] 
      index = parent_index 

Nun, ich benutze es als:

s = 'SORTEXAMPLE' 
a = BinaryHeap() 

for c in s: 
    a.insert(c) 

Jetzt danach wird der Haufen bestellt als:

['S', 'T', 'X', 'P', 'L', 'R', 'A', 'M', 'O', 'E', 'E'] 

statt

['X', 'T', 'S', 'P', 'L', 'R', 'A', 'M', 'O', 'E', 'E'] 

So scheint es, einer der letzten Austausch nicht passiert ist und ich dachte, ich hätte die Indexierung vermasselt, aber ich konnte keine offensichtlichen Probleme finden.

Answer 1

Ok, ich habe es herausgefunden. natürlich kann ich die parent_index nicht außerhalb der Schleife zwischenspeichern! sein

sollte der Code:

def __swim(self, index): 
    while index > 0 and self.heap[(index - 1) // 2] < self.heap[index]: 
     self.heap[(index - 1) // 2], self.heap[index] = self.heap[index], self.heap[(index - 1) // 2] 
     index = (index - 1) // 2 

Ich bin überrascht dies nicht vor in einer Endlos-Schleife gehen hat ....