세션8 우선순위 큐 pop함수의 Predicate 적용 관련 질문이 있습니다.

Question

pop 함수를 보면 if (right < (int)_heap.size() && predicate( heap[next], _heap[right])) 인 left와의 비교에서 나온 결과 값을 비교하는 부분에만 predicate를 적용하였는데 위에 left와 비교하는 부분은 둘 중 더 큰 값을 next에 넣는게 목적인 코드입니다. 더 작은값을 찾을때 문제가 생길 수 있을것이라 생각이 되는데 문제가 생기지 않아 의문점이 생겨 질문 드립니다. left쪽엔 predicate 비교를 하지 않아도 되는 이유가 무엇일까요?

Jeongmin Kim · Answer

그러게요. 보니까 left에도 predicate 처리를 해줘야 할 것 같아요. 하지 않으면 greater로 설정을 할 경우에 우선순위 큐의 동작이 이상해지네요.

serverdev · Answer

제 질문의 의도는 left는 두 값을 비교해서 무조건 더 큰 값을 반환하게 하는데 우선순위 큐는 상위에 있는 노드가 최대힙, 최소힙이냐에 따라 더 큰값 또는 더 작은 값이라는 조건만 있는것으로 알고 있습니다.

하지만 left에 predicate를 설정하지 않으면 무조건 처음엔 더 큰값을 반환하게 되는데 반환되지 않은쪽의 하위에 더 적당한 값이 있을 수 있을거 같아 질문 드렸습니다.

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. 서버공부중님. 우선순위 큐에서 Pop 함수는 일반적으로 힙 구조를 유지하는 과정에서 최상위 노드를 제거하고 나머지 노드를 재구성하는 역할을 합니다. 이때, Predicate 는 값 비교의 조건을 설정하기 위해 사용됩니다. 질문에서 언급한 Predicate 가 right 와의 비교에만 사용되고 left 와의 비교에는 사용되지 않는 것처럼 보일 수 있으나, 이는 구현 방식에 따라 다를 수 있습니다. Predicate 는 두 값을 비교하여 true 또는 false를 반환하는 함수 개념으로, 힙이 최소 힙인지 최대 힙인지에 따라 다르게 설정됩니다. 즉, 더 큰 값을 찾기 위한 과정에서 해당 비교 방식을 제공하는 것인데, 일반적으로 Predicate 는 모든 비교 연산에 적용될 것입니다. 코드가 한 부분에서만 Predicate 를 의식적으로 적용하고 다른 부분에서는 생략했다면 이는 작성자의 의도나 최적화 이유가 있을 수 있습니다. 다음의 게시물에서 Predicate 에 대해 조금 더 자세히 설명해주고 있으니, 참고하시면 도움이 될 것 같습니다: Container, Predicate 질문입니다. 위 링크에서는 Predicate 의 정의와 객체화에 대한 부분을 다뤘습니다. 이를 통해 Predicate 가 다양한 비교 상황에서 어떻게 쓰이는지 더 이해하실 수 있을 것입니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.