우선순위 큐 의 개념

Question

안녕하세요 루키스님. C++ 공부하다가 C# 넘어와서 배우는 중입니다. 우선순위 큐 강의로 처음 C# 우선순위 큐를 접하게 되었는데 C++에서 말하는 우선순위 큐와 조금 다른 것 같아서, 이를 이해하는데 어떻게 이해해야할지 감을 잡기가 어렵습니다. 구현해주신 우선순위 큐는 값들을 Add만 한 시점에서는 완벽한 우선순위 큐가 아닌 것으로 보입니다. 아무래도 Heap구조로 되어 있으니 왼쪽 브랜치와 오른쪽 브랜치의 비교가 완전하게 진행되진 않으니까요. 그래서 Add가 끝난 시점에 디버깅 포인트를 잡아놓고 값을 들여다보면 값들이 완전한 순서로 나열되어 있진 않습니다.  Pop을 통해 최대값/최소값을 뽑는데에는 최고의 방법이 맞지만 이 우선순위 큐의 용도가 그저 최대값/최소값을 쓰기 위한 용도라고 이해해야하는 건지, 아니면 C++ 에서 말하는 우선순위 큐 처럼 이해해도 무방한건지 헷갈립니다. 이전 강의 Heap 이론에서 조금 더 공부했을 때, MaxHeap과 MinHeap 개념이 있는 걸 알게되었는데요, 이 우선순위 큐가 MaxHeap과 같은 개념인 것으로 보여서, 여기서 또 헷갈렸습니다. 강의에 대해 의심하거나 하는 의도가 전혀 없고 절대 아닙니다! 그저 저는 게임개발을 배우고 있고 이 우선순위 큐가 C#에서 이런 구현방식으로 이용되기 때문에 이 방식으로 알려주시는 건지 궁금했고, C++의 우선순위 큐와 지금 알려주신 우선순위 큐의 개념이 조금 달라 어떻게 이해해야하는지 도움을 받고 싶어서 질문하는 것 뿐입니다. 또 MaxHeap과 같은 구조/이론 이라고 이해해도 되는지도 여쭤보고 싶습니다. 강의 잘 보고 있습니다 (: 좋은 강의 감사합니다!

Rookiss · Answer

그래서 Add가 끝난 시점에 디버깅 포인트를 잡아놓고 값을 들여다보면 값들이 완전한 순서로 나열되어 있진 않습니다.  -> '나열' 되어 있다는 것이 어떤 의미인지 모르겠습니다. 힙트리을 배열로 표현하는 것이지, 데이터가 배열에서 '나열' 되어 저장되는 것은 아닙니다. 그리고 애당초 이진평행트리가 아니기 때문에  부모/자식 관계에 대해서만 조건이 있지 왼쪽 오른쪽에 대해서 특별한 조건이 있진 않습니다. Pop을 통해 최대값/최소값을 뽑는데에는 최고의 방법이 맞지만 이 우선순위 큐의 용도가 그저 최대값/최소값을 쓰기 위한 용도라고 이해해야하는 건지, 아니면 C++ 에서 말하는 우선순위 큐 처럼 이해해도 무방한건지 헷갈립니다. -> C++에서 말하는 PriorityQueue랑 현재 다루는 PriorityQueue랑은 100% 동일한 내용입니다. C++에서는 std::priority_queue<T>를 사용하면 되고요. PQ는 원래 최소 혹은 최대값을 다루는데 최적화된 자료구조입니다. 이전 강의 Heap 이론에서 조금 더 공부했을 때, MaxHeap과 MinHeap 개념이 있는 걸 알게되었는데요, 이 우선순위 큐가 MaxHeap과 같은 개념인 것으로 보여서, 여기서 또 헷갈렸습니다. -> PriorityQueue를 어떻게 사용할지에 따라 Max/Min Heap 둘다 될 수 있습니다. 말 그대로 비교 조건만 반대로 하면 Min Heap이 되는 것이죠.  그저 저는 게임개발을 배우고 있고 이 우선순위 큐가 C#에서 이런 구현방식으로 이용되기 때문에 이 방식으로 알려주시는 건지 궁금했고, C++의 우선순위 큐와 지금 알려주신 우선순위 큐의 개념이 조금 달라 어떻게 이해해야하는지 도움을 받고 싶어서 질문하는 것 뿐입니다 -> 100% 동일한 개념입니다.