間違った結果

Question

私はオンラインコース以下のバイナリヒープを実装していますを与えるバイナリヒープ実装を作成し、私は次のように行われている：今

s = 'SORTEXAMPLE' 
a = BinaryHeap() 

for c in s: 
    a.insert(c) 

：今

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 

、私はそれを使用します

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

ではなく

：、この後のヒープは次のように命じています

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

だから、それは最後の取引所の一つが実現しなかったと私はインデックスを台無しにしているかもしれないと思ったが、私は任意の明白な問題を見つけることができなかったようです。

Answer 1

わかりました。もちろん、私はparent_indexをループ外にキャッシュすることはできません！

コードは次のようになります。

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 

私はこれは私が間違っている文字列を持っていた申し訳ありません前に....