인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

Inflearn Community Q&A

hyobinkim's profile image
hyobinkim

asked

[MMORPG Game Development Series with C# and Unity] Part 2: Data Structures and Algorithms

priority queue

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

Resolved

Written on

·

243

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를 쓰지 않는 것인지 이해가 쉽사리 되지가 않습니다

C#

Answer 7

1

rookiss님의 프로필 이미지
rookiss
Instructor

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

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

0

hyobinkim님의 프로필 이미지
hyobinkim
Questioner

정말 그렇네요

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

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

그래도 감사합니다!

0

rookiss님의 프로필 이미지
rookiss
Instructor

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

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

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

0

hyobinkim님의 프로필 이미지
hyobinkim
Questioner

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

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

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

0

rookiss님의 프로필 이미지
rookiss
Instructor

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

0

hyobinkim님의 프로필 이미지
hyobinkim
Questioner

덮어쓰기 인거네요

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

0

rookiss님의 프로필 이미지
rookiss
Instructor

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

hyobinkim's profile image
hyobinkim

asked

Ask a question