c++ - 将自定义数据插入priority_queue时出现invalid heap错误

Question

我现在正在尝试解决一个问题，该问题需要我在 2 维矩阵中找到前 k 个频繁出现的数字。

我定义了一个结构numCount，它有两个字段:number 用于存储数字，count 用于存储它出现的次数。然后我访问矩阵中的每个数字，如果它的 numCount 结构已经存在于最大堆中(按 count 排序)，我就增加它的 count由1；否则我会创建一个新的 numCount 对象并将其插入堆中。注意，为了高效的获取一个数对应的numCount对象，我保留了一个unordered_map来进行对应。

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

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]]

然后在尝试添加对应于 nums[1 处的第一个 3 的 numCount 对象时抛出 invalid heap 错误][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;
}

Answer 1

修改优先级队列中现有条目的键既是问题的原因，也是正确完成的巨大困惑。为了您的目的，根本没有必要这样做。
以递增方式保留优先级队列不会达到您已确定的目的，并且会使您的算法效率低下，并产生上述难以纠正的问题。

相反，您应该首先读取所有数据并计算所有计数。从数字到计数的映射对于那个阶段来说会简单得多，并且比您的额外间接级别更有效。

计算完所有计数后，您就可以找到最大的 k 个。优先级队列是寻找最大的 k 的好工具的一种可能性，但该队列的有效使用将涉及颠倒 k 的含义。构建一个最多可容纳 k 个项目的队列，并始终识别最小的(不是这 k 个项目中最大的)。在 Q 中插入前 k 个 number,count 对，然后对于其余的每一对，将其与 Q 中的最小值进行比较，如果新的是，则用新的对替换 Q 中的最小值比旧的最小的大。

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