Go to login Go to sub menu Go to text

데이터 구조 및 분석: Non-Linear Structure, Optimization, and Algorithms

임시 이미지 KAIST 산업및시스템공학과 문일철 교수
http://kaist.edwith.org/datastructure-2019s2/forum/13149
Thumb up 387 Learner 1116

binary heap에서 left child node의 index는 parent node *2이고, right child node는 parent node *2 +1 인 것으로 알고 있는데, 강의에서 제공되는 코드에서는 왜 아래(빨간색으로 표시한 부분)와 같이 표현이 되는지 궁금합니다.

defenqueueWithPriority(self,value,priority):

self.arrPriority[self.size]=priority

self.arrValue[self.size]=value

self.size=self.size+1

self.percolateUp(self.size-1)

 

defpercolateUp(self,idxPercolate):

ifidxPercolate==0: 

return

parent=int((idxPercolate-1)/2)

ifself.arrPriority[parent]<self.arrPriority[idxPercolate]: 

self.arrPriority[parent],self.arrPriority[idxPercolate]=self.arrPriority[idxPercolate],self.arrPriority[parent]

self.arrValue[parent],self.arrValue[idxPercolate]=self.arrValue[idxPercolate],self.arrValue[parent]

self.percolateUp(parent)

comment