C++ 에서 힙과 우선순위 큐에 대한 질문이 있습니다.

Question

Heap은 완전 이진 트리이지만, 노드, 포인터 기반이 아니라 배열 기반으로 만드는 걸로 알고 있습니다.우선순위 큐 또한 배열로 만들어진 힙을 기반으로 만든다고 알고 있구요.그렇다면, 아무래도 배열 기반이기 때문에 std::vector와 동일하게 reserve나 resize를 제대로 안해주면계속 메모리를 재 할당하면서 오버 헤드가 발생할 수 있지 않나 싶은 생각이 있습니다.그런데, 왜 std::priority_queue에는 reserve에 관한 멤버함수가 없을까요?인터넷에 올라오는 자료구조에 관한 자료를 찾아봐도 heap이나 우선순위 큐를 reserve하는 것에 대해 언급하시는 분들은 한 분도 없는데, 제가 잘못생각하고 있는걸까요?

개발잡부 · Answer

정확한 이유는 모르겠지만배열로 구현하면 조회가 O(1)이라는 장점이 있습니다.물론 밸런스 트리가 아닐경우 공간낭비가 심할수있는데힙은 완전이진트리니까 그럴일도 별로 없고삽입삭제에 따른 값 복사나 resize는 비용이긴한데, C++에서는 충분히 빠른 성능을 내줘서 무시해도 되는 오버헤드로 판단한게 아닐까합니다.그리고 reserve나 resize는 보통 사용자가 고려해야할 관심사항이 아니고STL에서 알아서 구현해놓은 내용이라서 알아서 해주겠거니~하고 신경안쓰셔도 될겁니다

n = n + 1 · Answer

힙 선언은 반드시 해제해야 메모리 누수가 발생하지 않습니다.일정 공간의 메모리 주소를 할당받고 해제 함으로 오버헤드가 발생하지 않습니다.오버헤드는 배열로 지정된 크기보다 넘는 위치를 참조할때 발생하는 것임으로 약간 이해가 다른듯 합니다.std::priority_queue 는 push pop 으로 데이터를 넣고 제거하여 사용함으로 내부적으로 힙영역을 제거하는 코드가 구현되어 있을 겁니다.

Hide_D · Answer

priority_queue의 구현이 꼭 heap으로만 정해져있는게 아니라서 reserve가 없을겁니다.단적으로 std::map 으로도 priority_queue를 구현할 수 있죠.

C++ 에서 힙과 우선순위 큐에 대한 질문이 있습니다.

3개의 답변

기술 목록