std :: priority_queue에서 std :: vector로 요소를 복사하는 방법

Question

예를 들어 입력 벡터에서 k 번째로 큰 요소를 골라 내고 싶습니다.

QuickSelect std :: nth_element를 사용하면 더 잘 수행 할 수 있습니다.

제 질문은이 코딩 문제를 해결하는 대신 std :: priority_queue의 기본 컨테이너 std :: vector를 다른 벡터로 복사하는 방법입니다.

priority_queue<int, vector<int>, greater<int>> pq; 
for (int num : nums) { 
    pq.push(num); 
    if (pq.size() > k) { 
     pq.pop(); 
    } 
} 

내 방법은 바보입니다 :

vector<int> res; 
while (!pq.empty()) { 
    res.push_back(pq.top()); 
    pq.pop(); 
} 

그것을 할 수있는 더 좋은 방법이 있나요?

우리는 최고 K 요소 주문 할 필요가 없습니다

vector<int> res = pq; 

처럼 그것을 할 수 있습니다.

Answer 1

아니요, 팝업없이 priority_queue의 모든 요소에 액세스 할 수 없습니다. 또한 요소를 외부로 옮기는 방법은 없지만 const 캐스트를 사용하는 방법이 있습니다. 정수의 경우에는 그만한 가치가 없지만 복사하는 데 비용이 많이 든다 고 상상해보십시오. 그 트릭은 pq가 그 자체가 const 저장소에 있지 않는 한 안전합니다 (즉, const로 시작하는 것으로 선언 됨). 이는 우선 순위 대기열에서는 드물기 때문입니다.

vector<int> res; 
while (!pq.empty()) { 
    res.push_back(std::move(const_cast<int&>(pq.top()))); 
    pq.pop(); 
} 

Answer 2

처음에는 vector<int>을 사용할 수 있습니다.

그리고이 벡터를 힙으로 처리하십시오 (std::make_heap, std::push_heap, std::pop_heap).

그런 식으로 벡터를 복사 할 수 있습니다.