c++ - 将自定义数据插入priority_queue时发生无效堆错误

我现在正在尝试解决一个问题，该问题要求我在k维矩阵中找到最常见的2频繁数。

我定义了具有两个字段的结构numCount：number用于存储数字，而count用于存储其出现时间。然后，我访问矩阵中的每个数字，如果其numCount结构已经存在于最大堆中（按count排序），则只需将其count增加1即可；否则，我将创建一个新的numCount对象并将其推入堆。请注意，为了有效地获取与数字相对应的numCount对象，我为它们的对应关系保留了unordered_map。

我的想法的主要逻辑如下代码所示。但是，在将某些push对象添加到堆之后，invalid heap操作会给出numCount错误。

struct numCount {
    int number;
    int count;
    numCount(int num) : number(num), count(1) {}
};

struct compare {
    bool operator() (numCount*& lhs, numCount*& rhs) {
        return lhs -> count > rhs -> count;
    }
};

vector<int> kPopular(vector<vector<int> >& nums, int k) {
    int m = nums.size(), n = nums[0].size();
    priority_queue<numCount*, vector<numCount*>, compare> pq;
    unordered_map<int, numCount*> mp;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mp.find(nums[i][j]) != mp.end())
                mp[nums[i][j]] -> count++;
            else {
                numCount* ncnt = new numCount(nums[i][j]);
                pq.push(ncnt); // This line gives the "invalid heap" error.
                mp[nums[i][j]] = ncnt;
            }
        }
    }
    vector<int> popular(k);
    for (int i = 0; i < k; i++) {
        popular[i] = pq.top() -> number;
        pq.pop();
    }
    return popular;
}

我在以下矩阵上测试此代码：

nums = [[1, 1, 2],
        [2, 2, 3]
        [1, 2, 3]]

然后，当尝试在invalid heap处添加与第一个numCount对应的3对象时，它将引发nums[1][2]错误。

如何解决此错误？

更新：在采纳@JSF的建议之后，我对代码进行了如下更新。

struct compare {
    bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) const {
        return lhs.second < rhs.second;
    }
};

vector<int> kPopular(vector<vector<int> >& nums, int k) {
    int m = nums.size(), n = nums[0].size();
    unordered_map<int, int> counts;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            counts[nums[i][j]]++;
    set<pair<int, int>, compare> st;
    for (auto pr : counts) {
        st.insert(pr);
        if ((int)st.size() > k)
            st.erase(st.begin());
    }
    vector<int> popular(k);
    set<pair<int, int>, compare>::iterator itr = st.begin();
    for (int i = 0; i < k; i++) {
        popular[i] = (*itr).first;
        itr = st.erase(itr);
    }
    return popular;
}

最佳答案

修改优先级队列中现有条目的键既是问题的原因，也是正确完成工作的一大麻烦。为了您的目的，根本不需要这样做。
保持优先级队列递增不会达到您已确定的目的，并使算法效率低下，还会产生上述难以纠正的问题。

相反，您应该首先读取所有数据并计算所有计数。从数字到计数的映射在该阶段将比您的间接级别更为简单，并且效率更高。

计算完所有计数后，即可找到最大的k个。优先队列是找到k最大的好工具的一种可能性，但是有效使用该队列将涉及反转k的意义。建立一个队列，该队列最多可容纳k个项目，并始终标识最小的队列（而不是k个项目中的最大队列）。在Q中插入前k对number,count对，然后将其余所有对与Q中的最小对进行比较，如果新的对大于旧的对，则用新的对替换最小的对。

如果您有充分的理由在计算计数时保持递增的Q，则该原因在您的帖子中并不明显，您应明确说明。使用支持更改现有项目的键的优先级队列并非不可能。我在自己的工作中很多地方都需要它，并选择编写自己的优先级队列（而不是使用std）来简化该方面。编写自己的代码并不难，但是也许还有一种使用std版本的方法。但是在进入这种复杂性之前，请解释问题的原因。

关于c++ - 将自定义数据插入priority_queue时发生无效堆错误，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31489275/