我需要使用堆,所以我搜索了 STL,但它似乎不起作用,我写了一些代码来解释我的意思:

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

struct data
{
    int indice;
    int tamanho;
};


bool comparator2(const data* a, const data* b)
{
    return (a->tamanho < b->tamanho);
}

int main()
{

        std::vector<data*> mesas;

        data x1, x2, x3, x4, x5;

        x1.indice = 1;
        x1.tamanho = 3;

        x2.indice = 2;
        x2.tamanho = 5;

        x3.indice = 3;
        x3.tamanho = 2;

        x4.indice = 4;
        x4.tamanho = 6;

        x5.indice = 5;
        x5.tamanho = 4;

        mesas.push_back(&x1);

        mesas.push_back(&x2);

        mesas.push_back(&x3);

        mesas.push_back(&x4);

        mesas.push_back(&x5);


        make_heap(mesas.begin(), mesas.end(), comparator2);

        for(int i = 0 ; i < 5 ; i++)
        {
            data* mesa = mesas.front();
            pop_heap(mesas.begin(),mesas.end());
            mesas.pop_back();

            printf("%d, %d\n", mesa->indice, mesa->tamanho);
        }

    return 0;
};

这就是我得到的:
4, 6
2, 5
1, 3
3, 2
5, 4

所以它不能作为堆工作,因为 vector 上的最大元素没有正确返回。

还是我做错了什么?

最佳答案

您需要将 comparator2 传递给 std::pop_heap,因为这就是您创建堆的方式。否则,它将对指针使用默认值小于运算符,该操作符仅比较指针值。

10-04 18:04