There is a question that states. Given an array obtain the 3rd highest element. Now suppose this is the array (lets assume that its sorted for now for simplicity - otherwise it can be unsorted)

//{1,2,3,4} -->Array under question. The answer is 2.

solution:

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();
}

I understand pretty much most of it. Except I have a hard time understanding the logic

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

Let me clarify I understand. The order of elements before the for loop in the Priority queue will be in ascending order so it will be 1,2,3

Now why are we checking if the last element in the array 4 is greater than the top element in the priority queue (which is 1) ? How does this check change the game so bad that if its greater we have to remove the lowest (which is 1) ? Any suggestions on this would be helpful

CodePudding user response：

The priority queue is created via pq(v.begin(), v.begin() n);, so it is of size n (3 in your example), and it is initialized to reference the first n elements of v. The top of the priority queue will always reference the element with the greatest priority in the queue. In this case, the element with the greatest priority is the smallest element. This is explained in the documentation, e.g. here; the compare operator provided (in this case std::greater<int>) returns true when a should come before b in the strict-weak ordering, and top() and pop() relate to the last element in the strict-weak ordering. As such, with std::greater<int>, we have a descending strict-weak ordering, and thus the smallest number is at the top.

Given that pq is of size n, and pq.top() refers to the smallest element in pq, then it is guaranteed that there are at least n - 1 elements greater than pq.top() at any given point (i.e. the rest of the elements in pq must be greater than it). So, you iterate over the remaining elements of v (skipping the first n elements from which the priority queue has already been initialized), and you check to see if any of them are also greater than pq.top(). If so, then there are at least n elements greater than pq.top(), and so pq.top() cannot be the nth greatest element. In such a case, you remove pq.top() via pq.pop(), and you push in this new larger element, which now takes the previous top element's place as a potential candidate as the nth greatest element.

By the end of the loop, pq will still be populated with n elements, and it is guaranteed that these are the n largest elements in v (otherwise, the smallest of the elements in pq would have been previously popped out or never pushed in to begin with, and thus you reach a proof by contradiction). As such, the smallest of these n elements must be the nth largest, and hence the function returns pq.top().

CodePudding user response：

You initially populate the priority queue with the first three elements of the vector v (this will be undefined behavior if v has fewer than 3 elements).

The priority queue uses std::greater for sorting, so the top of the queue is the smallest element in the queue.

In the loop, you compare the next element with the top of the queue, which is the third largest element that you know about so far. If it is larger, then the current third largest is fourth largest, and this next element is one of the largest three. The priority queue will figure out where it belongs.

When the loop is all done, you grab the 3rd largest element from the queue.