똑똑한 코드 작성을 위한 실전 알고리즘

140

똑똑한 코드 작성을 위한 실전 알고리즘

k

>

1

에 대해,

storage

[

k

]

에 있는 엔트리의 부모는

storage

[

k

//

2

]

에 있다. 여기서

k

//

2

는

k

를

2

로 나누고 소수점 이하를 버린 결과를 값으로 하는 정수다. 힙의 맨 꼭대기 엔트리

를

storage

[

1

]

에 저장했으므로 엔트리의 부모 위치를 계산하려면

2

로 나누기만 하면 된다.

5

//

2

=

2

이므로

storage

[

5

]

(우선순위가

11

)인 엔트리의 부모는

storage

[

2

]

에 있다.

storage

[

k

]

의 엔트리는 최대 힙의 엔트리 수가

N

일 때

0

<

k

≤

N

이면 유효하다.

2

×

k

>

N

일 때

storage

[

k

]

의 엔트리는 자식이 없다는 것이다. 예를 들어

2

×

10

=

20

>

18

이므로

storage

[

10

]

의 엔트리 (우선순위가

1

)는 왼쪽 자식이 없다. 또한

storage

[

9

]

(우연히도 우

선순위가

9

)의 엔트리는

2

×

9

+

1

=

19

>

18

이므로 오른쪽 자식이 없다.

4.5

엔트리 이동의 구현

최대 이진 힙을 저장하기 위해, 먼저

priority

와 연관된

value

를 가지는

Entry

를 구성하자.

class Entry:

def __init__(self, v, p):

self.value = v

self.priority = p

[코드

4

-

2

]는

storage

배열에 최대 이진 힙을 저장한다. 객체를 ...