C++ priority queue "greater" option is not working

Question

What is the problem?

When I use priority queue of STL, I want to use min heap, so I used like below code.

It works on default option but it is not working on "greater option".

It always arranges like above picture. I don't know totally why this happened.

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

If I understand your problem correctly, you are looking at a priority queue in a debugger and are confused as to why the items in the queue are not stored in the order you expected.

Priority queues do not guarantee to store items in priority order. They only guarantee to give you back items in priority order when you pop them off the queue. Keeping items in priority order would mean that it would have to perform a sort operation every time a new item what put on the queue, which would be inefficient. Instead, priority queues typically use a data structure called a heap to manage the queue, which allows for much more efficient insertions into the queue.