Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity? This is a rather well known solution to the $k$-th order statistic problem which requires us to find the $k$-th largest number in an unsorted array with $n$ elements where $1 \leq k \leq n$:
public int findKthLargest(int[] nums, int k) {
        PriorityQueue&lt;Integer&gt; heap = new PriorityQueue&lt;Integer&gt;();
        
        for (int num: nums) {
            heap.add(num);
            
            if (heap.size() &gt; k) {
                heap.remove();
            }
        }
        
        return heap.remove();
    }

A brief summary of this approach is that we maintain a min heap and keep polling from this heap each time its size exceeds $k$. This way, our final heap will contain $k$ elements, and these $k$ elements are guaranteed to be last $k$ elements in the sorted array  (since we have been polling minimums). Within these last $k$ elements, the minimum element is guaranteed to be the $k$-th largest so we extract the min and return that as a result.
What I don't particularly understand is why this problem is $\mathcal{O}(n \lg{(k)})$. For instance, after $\mathcal{O}(n)$ creation of the heap, we do an extraction of the minimum $n - k $ times, which would require sifting up in the heap $n - k$ times and hence, shouldn't this solution be $\mathcal{O}(n \lg{(n - k)})$?
Thanks!
The maximum number of elements in the heap at any given time is upper bounded by $k+1$.
Since each insertion or deletion from an heap requires $O(\log \eta)$ time where $\eta$ is the number of elements in the heap at the time of the operation, and $\eta \le k+1$, we know that each heap operation can be performed in time $O(\log (k+1) ) = O( \log k )$.
How many heap operations does the algorithm perform? Each element is inserted once, so there are $n$ insertions. In addition all but the largest $k-1$ elements are extracted. This yields a total of $n + (n-(k-1)) = 2n-k+1 = O(n)$ operations.
By multiplying the number of operations with our upper bound on the time required by each operation of $O(\log k)$  we obtain an overall time complexity of $O(n \log k)$.