关于优先级队列，有人可以向我解释一下这个逻辑吗？获得数组中的第 3 名

Question

有个问题说。给定一个数组，获取第三高的元素。现在假设这是数组（为简单起见，我们假设它现在已排序 - 否则它可以未排序）

//{1,2,3,4} --> 有问题的数组。答案是2。

解决方案：

int findnHighest(std::vector<int> v, int n=3)
{
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq(v.begin(), v.begin() + n);
    for (int i = n ; i < v.size(); i++) 
    {
        if (v[i] > pq.top()) 
        {
            pq.pop();
            pq.push(v[i]);
        }
    }
    return pq.top();
}

大部分我都听懂了。除了我很难理解逻辑

if (v[i] > pq.top()) 
{
    pq.pop();
    pq.push(v[i]);
}

让我澄清一下，我明白了。优先级队列中 for 循环之前的元素顺序将按升序排列，因此它将是 1,2,3

现在为什么要检查数组 4 中的最后一个元素是否大于优先级队列中的顶部元素（即 1）？这个检查如何改变游戏如此糟糕以至于如果它更大我们必须删除最低的（即 1）？对此的任何建议都会有所帮助

Answer 1

您最初使用向量 v 的前三个元素填充优先级队列（如果 v 的元素少于 3 个，这将是未定义的行为）。

优先级队列使用std::greater进行排序，因此队列的顶部是队列中最小的元素。

在循环中，您将下一个元素与队列顶部的元素进行比较，这是您目前已知的第三大元素。如果更大，则当前第三大的是第四大的，下一个元素是最大的三个之一。优先队列会找出它属于哪里。

当循环全部完成后，您从队列中获取第三大元素。

Answer 2

优先级队列是通过 pq(v.begin(), v.begin() + n); 创建的，因此它的大小为 n（在您的示例中为 3），并且它被初始化为引用 n 的第一个元素=13=]。优先级队列的顶部将始终引用队列中具有最高优先级的元素。在这种情况下，具有最高优先级的元素是 最小的 元素。这在文档中有解释，例如here;提供的比较运算符（在本例中为 std::greater<int>）returns true when a should come before b in the严格弱排序，top() 和 pop() 与严格弱排序中的最后一个元素相关。因此，对于 std::greater<int>，我们有一个降序的严格弱排序，因此 最小的 数字位于顶部。

鉴于pq的大小为n，而pq.top()指的是pq中的最小元素，则保证有至少 n - 1 个元素在任何给定点大于 pq.top()（即 pq 中的其余元素必须大于它）。因此，您遍历 v 的剩余元素（跳过优先级队列已经初始化的第一个 n 元素），然后检查是否有它们也大于 pq.top()。如果是，则至少有 n 个元素大于 pq.top()，因此 pq.top() 不可能是最大的 nth 元素。在这种情况下，您通过 pq.pop() 删除 pq.top()，然后推入这个新的更大的元素，它现在取代前一个顶部元素的位置，成为 nth 最大元素的潜在候选者。

到循环结束时，pq 仍将填充 n 个元素，并且保证这些是 v 中最大的 n 个元素（否则，pq 中最小的元素之前可能会被弹出或从未被推入，因此您可以通过反证法得到证明）。因此，这些 n 元素中最小的必须是最大的 nth，因此函数 returns pq.top().

关于优先级队列，有人可以向我解释一下这个逻辑吗？获得数组中的第 3 名

Can someone please explain this logic to me when it comes to a priority queue. Get the 3rd highest in the array

c++

logic

priority-queue