해결된 질문
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
2024. 09. 09. 16:14
직접 프로젝트를 만들어서 PQ 부분을 떼서 실험을 해보고 디버깅을 해보시기 바랍니다.
그리고 위 예제에서 보여주신 트리 구조는 힙 트리를 처음부터 만족하지 않아서, 반례가 되지 않습니다.
(Child의 Value가 Parent의 Value보다 커야 하는데 그 조건이 깨진 상태)
2024. 09. 09. 17:15
감사합니다 :)