make_heap과 priority_queue는 언제 사용해야합니까?

Question

힙을 만드는 데 사용할 벡터가 있습니다. 나는 C++ make_heap 함수를 사용해야하는지 내 벡터를 우선 순위 대기열에 넣어야하는지 잘 모르겠다. 성능 측면에서 어느 것이 더 낫습니까? 언제 다른 제품을 사용해야합니까?

Answer 1

성능의 차이는 없습니다. std::priority_queue은 컨테이너와 매우 동일한 힙 관련 함수 호출을 클래스로 래핑하는 어댑터 클래스입니다. std::priority_queue의 명세에는 공개적으로 그 내용이 나와 있습니다.

노출 된 std::vector에서 힙 기반 우선 순위 큐를 생성하면 (힙 관련 함수를 직접 호출하여) 외부 액세스가 가능할 수 있으므로 힙/큐의 무결성이 손상 될 수 있습니다. std::priority_queue은 "표준"최소값에 대한 액세스를 제한하는 장벽 역할을합니다. push(), pop(), top() 등. 자체 규율 시행 조치로 볼 수 있습니다.

또한 큐 인터페이스를 "표준"작업 세트에 적용함으로써 동일한 외부 사양을 준수하는 다른 클래스 기반 우선 순위 큐 구현과 동일하게 상호 교환 할 수 있습니다.

Answer 2

priority_queue는 (적어도 정상적으로) 힙으로 구현됩니다. 따라서, 진짜 질문은 priority_queue가 필요한 것을 제공하는지 여부입니다. make_heap을 사용할 때 여전히 모든 요소에 액세스 할 수 있습니다. priority_queue를 사용하면 요소에 매우 제한된 액세스 권한을 부여하는 작업이 거의 없습니다 (기본적으로 항목을 삽입하고 대기열의 헤드에서 항목을 제거함).

Answer 3

priority_queue은 (는) 컨테이너가 아닙니다. 특정 기본 컨테이너를 사용하는 컨테이너 어댑터입니다. vector 또는 deque이며 데이터 작업을위한 특정 메소드 세트를 제공합니다. 또한 구현은 *_heap 알고리즘을 사용합니다.

예를 들어 vector에 새 값을 입력 할 때마다 push_heap을 호출하여 힙으로 간주되는 범위를 확장해야합니다. priority_queue을 사용하지 않으면 vector의 절반을 힙 (std::make_heap(v.begin(), v.begin() + (v.size()/2)))으로 간주 할 수 있으며 나머지 절반은 그대로 유지할 수 있습니다. 당신이 그것을에 push를 호출 할 때

무엇 priority_queue을 수행합니다 그것은 기본 컨테이너의 뒷면에 새로운 요소를 밀어 (단지 가장 큰 것으로 첫 번째 요소를 중요) 우선 순위 힙 속성을 유지하기 위해 push_heap를 호출합니다.

성능 문제보다는 솔루션 디자인과 특정 요구 사항을 고려하는 것이 좋습니다.

Answer 4

벡터를 수정하고 싶지 않으면 별도의 벡터를 생성하므로 우선 순위 대기열을 사용해야합니다 (추가 공간 필요). 또한 구현하기 쉽습니다. 예를 들어, 요소를 팝핑하는 동안 make_heap을 사용할 때는 우선 pop_heap과 pop_back .. 두 가지 명령을 사용해야하지만 우선 순위 큐의 경우에는 하나의 명령으로 수행 할 수 있습니다. 마찬가지로 요소를 힙으로 밀어 넣는 동안.
우선 순위 큐는 컨테이너가 아니며 make_heap 작업에서 사용하는 것과 동일한 힙 작업을 사용하는 벡터 또는 deque로 기본 컨테이너를 사용하기 때문에 둘 다 성능이 같습니다. 따라서 요구 사항에 따라 하나를 사용해야합니다 .