将自定义数据推入 priority_queue 时出现无效堆错误

Question

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

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

我的思路主要逻辑如下代码所示。但是，push 操作在将一些 numCount 对象添加到堆后给出 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][2] 处的第一个 3 的 numCount 对象时抛出 invalid heap 错误。

我该如何修复这个错误？

更新：在采纳@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，那么您的 post 中并不明显，您应该明确这一点。使用支持更改现有项目键的优先级队列并非不可能。我在我自己的工作中的很多地方都需要它，并选择编写我自己的优先级队列（而不是使用 std）以使这方面更容易。自己编写代码并不难，但可能还有一种使用 std 版本的方法。但在进入那种复杂性之前，请解释为什么这个问题需要它。

将自定义数据推入 priority_queue 时出现无效堆错误

invalid heap error when pushing self-defined data into the priority_queue

c++

heap

priority-queue