잘못된 결과

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 

나는이 전에 무한 루프에 가지 않았다 놀란다는 ....