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를 쓰지 않는 것인지 이해가 쉽사리 되지가 않습니다
Answer 7
1
왼쪽/오른쪽 두 값 모두 현재값보다 크면,
무조건 왼쪽으로 가는게 아니라
왼쪽/오른쪽 중에서 더 큰쪽으로 이동해야 하기 때문입니다.
첫 if는 왼쪽과 비교해서 더 크면 왼쪽으로 이동하는 구문인데,
끝판왕이 오른쪽인 상황이 있다면 왼쪽 이동을 취소하고
오른쪽으로 다시 마음을 다잡기 위해 한 번 더 비교를 해주고 있습니다.
0
정말 그렇네요
뭐랄까 이전에도 이와 비슷한 경우가 있었던거 같은데
이 처럼 코드에서 보여지는 거 외에 뭔가 더 생각해봐야 될 게 있는 경우는 시간이 걸리네요 이해하기 까지
그래도 감사합니다!
0
만약에 now 값보다 left값, right값 둘다 크다면,
무조건 오른쪽으로 진행하도록 짜여진거라고 보면 되는군요?
-> 그렇지 않습니다.
코드를 유심히 보면 둘 다 now보다 클 경우
left, right 중에 더 큰 쪽으로 이동하게 되어 있습니다.
next = left로 먼저 왼쪽으로 이동하게 설정한 다음,
다음 if에서 _heap[next]와 _heap[right]을 비교하니
만약 여기서 left다 더 크면 끝나고
아니면 next = right을 하게 됩니다.
0
만약에 now 값보다 left값, right값 둘다 크다면,
무조건 오른쪽으로 진행하도록 짜여진거라고 보면 되는군요?
이래도 되는 이유는 이진트리와는 다르게 왼쪽 오른쪽 상관없이 차일드 노드의 값이 더 작기만 하면 되고, 항상 왼쪽부터 채워진다는 특성들 때문인가요?
0
0
0
물론 if가 연속해서 나오는게 싫다면,
먼저 왼쪽/오른쪽 중 더 큰 값이 어느쪽인지를 구한 다음
그 부분과 now를 비교해서 한 번에 처리하는 것도 괜찮습니다.