C++ 우선 순위 큐가 정렬하지 않는다

-3

사용자 지정 클래스와 비교 구조체를 사용하여 C++에서 우선 순위 큐를 구현하려고 시도했지만 새 요소를 누를 때마다 큐 자체가 정렬되지 않습니다. 헤더에서C++ 우선 순위 큐가 정렬하지 않는다

private: 
    std::priority_queue<Node*, std::vector<Node*>, NodeCompare> queue;

구조체 :

Node* node = new Node(nrInTree, value); 
queue.push_back(node);

어떤 아이디어 : 클래스에서

struct NodeCompare 
{ 
    bool operator()(Node* n1, Node* n2) 
    { 
     int val1 = n1->getValue(); 
     int val2 = n2->getValue(); 
     return val1 < val2; 
    } 
};

출처

2014-10-22 MrWonderland

"자체를 분류하지 않음"이란 무엇을 의미합니까? 어떤예요? –

또한,'operator()'는'const'이어야합니다. –

엘리먼트를 푸시하면 큐가 자동으로 CompareStruct에 따라 스스로를 주문한다는 것을 이해했습니다. 그래서 내 경우 값 5,9,6 (순서대로)이 3 개의 노드를 밀어 넣으면 대기열 자체가 5,6,9로 정렬됩니다. 맞습니까? 아니면 개념을 잘못 이해합니까? – MrWonderland

코드가 정확합니다. 하지만 여기서 오해 한 것 같아요. priority_queue는 데이터 구조 힙을 사용하여 구현되기 때문에. 아시다시피, 힙은 정렬되지 않습니다. 최대 요소 인 이 맨 앞에 있다는 속성 만 있습니다. 매번 요소를 힙에 삽입하면 힙은 O (lgN) 시간을 사용하여 최대 값을 앞쪽으로 밀어 넣습니다. 그리고 요소를 팝 할 때마다 가장 큰 요소가 얻어집니다. 그러나 힙은 전혀 정렬되지 않습니다.

출처

2014-10-22 14:54:53 ljshou

C++ 우선 순위 큐가 정렬하지 않는다

답변

관련 문제