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 < minHeap.count             insert current element to maxHeap // O(log(n))          else:             insert current element to minHeap // O(log(n))     3. if maxHeap.count < 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))?
Algorithm to find k elements following the median in sorted order
algorithms;sorting;arrays;heaps
Answering your second question:Find the median $m$, and partition the set into $L_1 = \{x | x \in S \wedge x < m\}$ and $L_2 = \{x | x \in S \wedge x > 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 > 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.