将对象推入向量然后将向量推入堆时堆无效

Question

我在这里尝试使用 class Bar 来存储 Foo 的有序数组，其成员 var 如下所示。

我期待这样的输出 3,4,5 但我得到 5,3,4.

我正在使用我自己的比较函数（强制性的，因为我的 Foo struct 有更多数据）并且在推回向量后，我将向量推回堆并重新排序。

我在这里错过了什么？

我想要的是将一个Foo对象推入我的队列，并自动重新排序。

struct Foo
{
    int var;
    //etc.
};

struct compare
{
   bool operator()(const Foo& s1, const Foo& s2)
   {
       return s1.var < s2.var;
   }
};

class Bar
{
private:
    std::vector<Foo> m_vector;
public:
    Bar() 
    {
        std::make_heap(m_vector.begin(), m_vector.end(), compare());
    }

    ~Bar() {}

    void push (const Foo& t)
    {
        m_vector.push_back(t);
        std::push_heap(m_vector.begin(),m_vector.end(), Comp());
    }

    void pop()
    {
        m_vector.pop_back();
    }

    void dump(void)
    {
        printf ("\n Dumping:");
        for(int i = 0; i < m_vector.size() ; i++)
        {
            printf ("%d ", m_vector.at(i).var);
        }
        printf ("\n");
    }
};

int main() 
{
    Bar myBar;

    myBar.dump();

    Foo t1;
    t1.var = 3;

    myBar.push(t1); 
    myBar.dump();

    Foo t2;
    t2.var = 4;

    myBar.push(t2); 
    myBar.dump();

    Foo t3;
    t3.var = 5;

    myBar.push(t3); 
    myBar.dump();

    return 0;
}

Answer 1

如果您以相反的顺序获取对象，那么您应该切换比较信号：

bool operator()(const Foo& s1, const Foo& s2)
{
   return s1.var > s2.var;
}

但是，您似乎没有正确理解堆。堆不保留已排序的对象，而只是部分排序。请注意，它们仍然会按顺序弹出对象，但您需要实际弹出它们，只是迭代堆不会这样做。

注意下图中数组根本没有排序。但是，当呈现为树时，堆确实拥有一个重要的属性：每个节点都小于其所有后代。这就是 partially sorted 的意思。对象未排序，但它们以一种可以有效排序的方式相互关联。

要让您的元素恢复排序，您需要弹出它们。

编辑：顺便说一句，你应该使用 std::pop_heap，而不是 std::vector::pop_back。原因经过前面的解释应该就清楚了

将对象推入向量然后将向量推入堆时堆无效

Invalid heap while pushing object into vector and then pushing vector into heap

c++

sorting

heap

vector