우선 순위 대기열의 순서가 잘못됨

Question

나는 허프만 인코딩을 프로그래밍하고 있습니다. 이것은 내 프로그램의 시작입니다 :

using namespace std; 

//Counting methods 
int *CountCharOccurence(string text) 
{ 
    int *charOccurrence = new int[127]; 
    for(int i = 0; i < text.length(); i++) 
    { 
     charOccurrence[text[i]]++; 
    } 
    return charOccurrence; 
} 

void DisplayCharOccurence(int *charOccurrence) 
{ 
    for(int i = 0; i < 127; i++) 
    { 
     if(charOccurrence[i] > 0) 
     { 
      cout << (char)i << ": " << charOccurrence[i] << endl; 
     } 
    } 
} 

//Node struct 
struct Node 
{ 
    public: 
     char character; 
     int occurrence; 

     Node(char c, int occ) { 
      character = c; 
      occurrence = occ; 
     } 

     bool operator < (const Node* node) 
     { 
      return (occurrence < node->occurrence); 
     } 
}; 

void CreateHuffmanTree(int *charOccurrence) 
{ 
    priority_queue<Node*, vector<Node*> > pq; 
    for(int i = 0; i < 127; i++) 
    { 
     if(charOccurrence[i]) 
     { 
      Node* node = new Node((char)i, charOccurrence[i]); 
      pq.push(node); 
     } 
    } 

    //Test 
    while(!pq.empty()) 
    { 
     cout << "peek: " << pq.top()->character << pq.top()->occurrence << endl; 
     pq.pop(); 
    } 
} 

int main(int argc, char** argv) { 

    int *occurrenceArray; 
    occurrenceArray = CountCharOccurence("SUSIE SAYS IT IS EASY"); 
    DisplayCharOccurence(occurrenceArray); 
    CreateHuffmanTree(occurrenceArray); 

    return (EXIT_SUCCESS); 
} 

프로그램은 먼저 발생 숫자와 함께 문자를 출력합니다. 이것은 미세 같습니다

 : 4 
A: 2 
E: 2 
I: 3 
S: 6 
T: 1 
U: 1 
Y: 2

하지만 우선 순위 출력이 노드의 내용을 표시하는 테스트 루프 :

peek: Y2 
peek: U1 
peek: S6 
peek: T1 
peek: I3 
peek: E2 
peek: 4 
peek: A2

이 예상 순서가 아니다. 왜?

Answer 1

우선 순위 대기열에 정렬 기준을 알려야합니다. 당신의 경우에, 당신은 Node::occurence에 의하여 분류하기 위하여 그것을 말해야한다.

Answer 2

우선 순위 큐의 요소는 포인터입니다. Node 객체에 2 개의 포인터를 사용하는 함수를 제공하지 않으므로 기본 비교 함수는 2 개의 포인터를 비교합니다.

bool compareNodes(Node* val1, Node* val2) 
{ 
    return val1->occurence < val2->occurence; 
} 
priority_queue<Node*, vector<Node*>,compareNodes > pq; 

포인터를 비교함으로써, 기지국은 기지국 *

Answer 3

대기열에서 노드에 대한 포인터를 저장되지만, 적절한 비교 함수를 제공하지와 비교할 때 통신사 < 사용되므로, 이들은 정렬 . 제공 한 operator<은 노드와 포인터를 비교합니다. 원하는 것은 아닙니다.

이 두 가지있다 :

• 그들의 값에 따라 두 개의 노드 포인터를 비교하는 기능을 제공하며, 큐에이 기능을 제공하거나, 큐
• 저장 노드 객체 및 제공 operator< 두 노드를 비교하십시오.

두 번째 옵션은 코드에서 메모리 누수를 수정하고 불필요한 메모리 할당을 제거하므로 제안 할 것입니다.