• 카테고리

    질문 & 답변
  • 세부 분야

    게임 프로그래밍

  • 해결 여부

    해결됨

이 부분이 이해가 잘 안갑니다

21.01.13 01:37 작성 조회수 186

0

        public int Pop()
        {
            // Create a variable storing the return value
            int ret = _heap[0];

            // Rearrange the Heap since the root node is removed
            // move the very last data into the root node
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);
            lastIndex--;

            // Value comparision downwards begins
            // the index of the current node
            int now = 0;
            while(true)
            {
                // the indices of the child nodes
                int left = 2 * now + 1;
                int right = 2 * now + 2;

                int next = now;

                // move to the left if the left value is bigger
                if (left < lastIndex && _heap[next] < _heap[left])
                    next = left;
                // move to the right if the right value is bigger, which contains the previous case as well (that's why it's not else if)
                if (right < lastIndex && _heap[next] < _heap[right])
                    next = right;
                // Exit the loop if the left/right values are smaller than the current value
                if (next == now)
                    break;

                // Exchange the values
                int temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // Move to the next index
                now = next;
            }

            return ret;
        }

우선순위큐의 Pop 함수에서, 

저기 if 구문 3개가 나오는 부분에서 어째서 else if를 쓰지 않는 것인지 이해가 쉽사리 되지가 않습니다

답변 7

·

답변을 작성해보세요.

1

왼쪽/오른쪽 두 값 모두 현재값보다 크면,
무조건 왼쪽으로 가는게 아니라
왼쪽/오른쪽 중에서 더 큰쪽으로 이동해야 하기 때문입니다.

첫 if는 왼쪽과 비교해서 더 크면 왼쪽으로 이동하는 구문인데,
끝판왕이 오른쪽인 상황이 있다면 왼쪽 이동을 취소하고
오른쪽으로 다시 마음을 다잡기 위해 한 번 더 비교를 해주고 있습니다.

0

Hyobin Kim님의 프로필

Hyobin Kim

질문자

2021.01.14

정말 그렇네요

뭐랄까 이전에도 이와 비슷한 경우가 있었던거 같은데

이 처럼 코드에서 보여지는 거 외에 뭔가 더 생각해봐야 될 게 있는 경우는 시간이 걸리네요 이해하기 까지

그래도 감사합니다!

0

만약에 now 값보다 left값, right값 둘다 크다면,
무조건 오른쪽으로 진행하도록 짜여진거라고 보면 되는군요?

-> 그렇지 않습니다.
코드를 유심히 보면 둘 다 now보다 클 경우
left, right 중에 더 큰 쪽으로 이동하게 되어 있습니다.

next = left로 먼저 왼쪽으로 이동하게 설정한 다음,
다음 if에서 _heap[next]와 _heap[right]을 비교하니
만약 여기서 left다 더 크면 끝나고
아니면 next = right을 하게 됩니다.

0

Hyobin Kim님의 프로필

Hyobin Kim

질문자

2021.01.13

만약에 now 값보다 left값, right값 둘다 크다면,

무조건 오른쪽으로 진행하도록 짜여진거라고 보면 되는군요?

이래도  되는 이유는 이진트리와는 다르게 왼쪽 오른쪽 상관없이 차일드 노드의 값이 더 작기만 하면 되고, 항상 왼쪽부터 채워진다는 특성들 때문인가요?

0

어느쪽이 더 큰지는 굳이 기억할 필요 없습니다!
어차피 now에 둘 중 큰 값이 들어가 있을테니,
나머지 로직은 동일하게 실행될겁니다.

0

Hyobin Kim님의 프로필

Hyobin Kim

질문자

2021.01.13

덮어쓰기 인거네요

그런데 저렇게 되면 왼쪽/오른쪽 중 어디가 더 큰건지는 모르게 되는거 아닌가요?

0

물론 if가 연속해서 나오는게 싫다면,
먼저 왼쪽/오른쪽 중 더 큰 값이 어느쪽인지를 구한 다음
그 부분과 now를 비교해서 한 번에 처리하는 것도 괜찮습니다.