his130   1년 전

최대힙 구하는 문제를 아래와 같이 pop , push 함수로 나눠서 나타냈습니다.


그런데 다름이 아니라

pop 함수의 for 문에서 i의 조건문을 

i*2+1 <= last; 

하니 틀렸습니다가 나왔습니다.

그리고 i*2<=last 로 하니 맞았습니다가 나왔습니다.

for문 안에서 가장 최대값까지 설정해줬는데 왜 두개가 다른지 잘 모르겠습니다...ㅠㅠ

RiKang   1년 전

i의 자식이 1개일 때가 다릅니다.

i의 자식 노드중에서 i*2 는 존재하고, i*2+1 는 존재하지 않는 경우입니다.

그런 경우에도 heap[i*2] > heap[i] 라면 둘을 스왑해야 합니다.

위의 소스에서 i=1 , last = 2 인 경우를 생각해보면 heap[1] 과 heap[2] 를 비교해봐야 하는데, 그 전에 i*2+1<=last 에 걸려서 반복문이 그대로 끝나버립니다. 

his130   1년 전

아하 그렇군요..

i*2 노드는 존재하지 않고 i*2+1 노드는 존재하는 경우는 없기 때문인거죠?

RiKang   1년 전

네, 힙의 구현 특성상 i*2+1 노드가 존재하면 i*2 노드도 존재하기 때문에

for 안에 들어가야할 ( 자식 노드가 존재하는가? ) 이런 조건이

자식 노드가 존재하는가?

-> 왼쪽 노드가 존재하는가? || 오른쪽 노드가 존재하는가?

-> i*2 노드가 존재하는가? || i*2+1 노드가 존재하는가? 

-> i*2 <= last || i*2+1 <= last

-> i*2 <= last

이런식으로 단순화 되는 것 같습니다.

his130   1년 전

친절한 설명 정말 감사드립니다! 복받으세요

댓글을 작성하려면 로그인해야 합니다.