关于priority_queue的一个问题

时间:2021-09-09 17:39:20

我说之前project1运行总有问题,果然这个优先队列用法不了解出错了,可惜现在才看到,要不8puzzle应该能够正确完成。记下来

priority_queue只会在push的时候进行排序,因此,先push,再对元素进行修改,并不会改变priority_queue的排序。举一个例子

        priority_queue<s*, vector<s*>, cmpLarge> openlist;
        s* s1 = new s;
        s* s2 = new s;
        s1->a = 1;
        s1->b = 1;
        s2->a = 2;
        s2->b = 2;
        openlist.push(s1);
        openlist.push(s2);
        cout << openlist.top()->a << " " << openlist.top()->b << endl;
        s2->a = 0;
        s2->a = 0;
        cout << openlist.top()->a << " " << openlist.top()->b << endl;

openlist是针对s->a+s->b进行排序,程序得到的结果是
1 1
1 1
这说明我们在对openlist进行push了s1和s2之后,先调用一次openlist.top(),会返回s1,然后我们对s2进行修改,让它的a+b值为0,但是第二次调用openlist.top()时,得到的依然是s1。
 关于priority_queue的一个问题

aa.png (740.68 KB, 下载次数: 0)

下载附件

2016-3-23 14:56 上传



在伪代码中,在openlist.push()之前,应该先计算好successors的g和h值,再对它进行push。否则openlist.top()可能返回的不是g+h最小的那个节点。