인프런 커뮤니티 질문&답변

xkdl780님의 프로필 이미지

작성한 질문수

[Rookiss 켠김에 출시까지] 유니티 캐주얼 모바일 MMORPG (M2)

JobTimer 클래스의 우선순위 큐 질문

해결된 질문

24.09.09 16:08 작성

·

33

0

안녕하세요.

JobTimer 클래스에서 사용된 우선순위 큐 관련해서 2가지 궁금한 점이 있습니다.

1. 여기서 사용된 우선순위 큐는 최소힙으로 구현된게 맞나요?

PriorityQueue.cs 에 작성된 우선순위 큐는 최대힙 이지만, JobTimerElem 구조체를 정의할 때 CompareTo 메서드를 오버라이딩 해서 최소힙을 사용하게끔 수정한 것으로 이해했는데 제대로 이해한게 맞을까요?

2. Pop 메서드에서 힙 정렬 과정 질문

PriorityQueue.cs에 작성된 Pop 메서드의 While 문이 힙 정렬을 담당하는 부분으로 이해했습니다.

만약 While 문 한 번으로 정렬이 끝나지 않는 경우는 어떡하나요?
예를 들어 다음과 같이 저장된 최소 힙의 경우
이렇게 While문이 한 번 끝났는데 최솟값인 2가 루트 위치에 있지 않은 경우가 있어서 질문 드립니다.

답변 1

0

Rookiss님의 프로필 이미지
Rookiss
지식공유자

2024. 09. 09. 16:14

직접 프로젝트를 만들어서 PQ 부분을 떼서 실험을 해보고 디버깅을 해보시기 바랍니다.
그리고 위 예제에서 보여주신 트리 구조는 힙 트리를 처음부터 만족하지 않아서, 반례가 되지 않습니다.
(Child의 Value가 Parent의 Value보다 커야 하는데 그 조건이 깨진 상태)

xkdl780님의 프로필 이미지
xkdl780
질문자

2024. 09. 09. 17:15

감사합니다 :)

xkdl780님의 프로필 이미지

작성한 질문수

질문하기