Algorithm to find k elements following the median in sorted order I have the following problem:

Given an unsorted array A of size n, print the first k elements in A larger than its median.

Here's my approach to the problem:

     1. Create a minHeap and a maxHeap
     2. Iterate over elements in A // O(n)
        - if maxHeap.count &lt; minHeap.count
             insert current element to maxHeap // O(log(n))
          else:
             insert current element to minHeap // O(log(n))
     3. if maxHeap.count &lt; minHeap.count:
              median = minHeap.extractMin()
     4.  output k elements from minHeap  // O(klog(n))


This maintains a maxHeap of elements less than the median and a minHeap of elements greater than or equal to the median. But from my analysis, this seems to take O(nlogn + k(log(n)) which is no better than sorting A first and grabbing A[n/2:n/2+k] in just O(nlog(n) + k).

Now I have 2 questions:


Is my analysis tight? I am doubtful since the heaps have at most i elements in the ith iteration, not n.
Is there a better algorithm? Maybe something like O(n+klog(k))?
Answering your second question:


Find the median $m$, and partition the set into $L_1 = \{x | x \in S \wedge x &lt; m\}$ and $L_2 = \{x | x \in S \wedge x &gt; m\}$.
Find the $k$th largest element $x_k$ in $L_2$, and partition the set into $L_2' = \{x | x \in L_2  \wedge x \leq x_k\}$ and $L_3 = \{x | x \in L_2 \wedge x &gt; x_k\}$.
Sort $L_2'$ and return.


Steps 1 and 2 take $O(n)$. Step 3 takes $O(k \log k)$. Total time $O(n + k \log k)$.

Note this assumes distinct values. Repeated values involves some edge case handling.