Repository navigation
p450 힙 구현에서 _percolate_up 함수 분기 #156
Description
def _percolate_up(self):
i = len(self)
parent = i // 2
while parent > 0:
if self.items[i] < self.items[parent]:
self.items[parent], self.items[i] = self.items[i], self.items[parent]
i = parent
parent = i // 2
현재 책에서는 min heap 구현 시 위와 같이 삽입된 노드가 그 부모보다 작지 않을 때 swap은 하지 않고 계속 위로 percolate 하도록 되어있습니다.
이때 아래처럼 break을 걸어 percolate을 멈춰야 하지 않나요?
def _percolate_up(self):
i = len(self)
parent = i // 2
while parent > 0:
if self.items[i] < self.items[parent]:
self.items[parent], self.items[i] = self.items[i], self.items[parent]
i = parent
parent = i // 2
else:
break
Activity
likejazz commentedon Apr 12, 2022
안녕하세요. 멈추지 않더라도 제대로 정렬이 되어 있다면 어차피 더 이상 swap이 일어나지 않기 때문에 틀린 코드는 아닙니다. 하지만 말씀하신대로 중간에 멈추면 불필요한 연산을 줄일 수 있을거 같네요. 알려주셔서 감사합니다.