c++ - C++ 优先级队列“更大”选项不起作用

Question

问题是什么？

当我使用 STL 的优先级队列时，我想使用最小堆，所以我使用如下代码。

它适用于默认选项，但不适用于“更大的选项”。

它总是像上图一样排列。我完全不知道为什么会这样。

struct node {
    string code;
    int fre;

    bool operator<(const node& rhs) const {
        return fre < rhs.fre;
    }

    bool operator>(const node& rhs) const {
        return fre > rhs.fre;
    }
};

std::priority_queue<node, vector<node>, greater<node>> q;
std::map<node,int> huffman_tree;

int main(void)
{
    int f;
    for (int i = 1; i <= n; i++) {
        string c;
        std::cin >> c >> f;
        node huffman = { c,f };
        q.push(huffman);
    }

    q.pop();

    return 0;
}

Answer 1

如果我正确理解您的问题，那么您正在调试器中查看优先级队列，并且对为什么队列中的项目未按您预期的顺序存储感到困惑。

优先队列不保证按优先顺序存储项目。他们只保证在您将物品从队列中弹出时按优先顺序归还您。将项目保持在优先级顺序意味着每次将新项目放入队列时都必须执行排序操作，这将是低效的。相反，优先级队列通常使用称为堆的数据结构来管理队列，这允许更有效地插入队列。