优先队列顺序错误

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

这不是预期的顺序。为什么？

- TheArchitect

Answer 1

你的优先队列中的元素是指针。由于你没有提供一个接受两个Node对象指针的函数，所以默认比较函数会比较两个指针。

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

当 Node 与 Node* 进行比较时，您使用运算符 <。

- a1ex07

Answer 2

你应该告诉你的优先队列按什么排序。在你的情况下，你必须告诉它按 Node::occurence 排序。

- David Sauter

Answer 3

您正在将节点指针存储在队列中，但没有提供适当的比较函数，因此它们是通过比较指针进行排序的。您提供的 operator< 将会比较一个节点和一个指针，这不是您想要的。

有两个选项：

• 提供一个函数来根据其值比较两个节点指针，并将此函数提供给队列；或者
• 将节点对象存储在队列中，并提供一个 operator< 来比较两个节点。

第二个选项还将修复您代码中的内存泄漏，并删除一堆不必要的内存分配，因此我建议使用第二个选项。

- Mike Seymour

---

谢谢，现在它可以工作了。我已经从事编程一段时间了，但是对于C++来说还是新手。我必须说，你越了解这门语言，就会越喜欢它。但是我认为刚开始的时候很难。 - TheArchitect