0
$\begingroup$

What is the complexity of finding the k'th largest element in an unsorted linked list? If we sort the list, I think that the complexity is O(nlogn + k)=O(nlogn) since k < n. Is there a way of finding the kth largest element without sorting the list?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jul 4 '17 at 22:34
1
$\begingroup$

Yes, there is. Selection algorithm. There are two versions: running in worst-case linear time, and in expected linear time (see Cormen's chapter 9). You can also implement this algorithm to run in sublinear time using data structures.

$\endgroup$
0
$\begingroup$

You don't need to sort the list for finding $k$-th largest element. You can use Max Heap data structure .

Algorithm $(A,k)$

  1. Build Max-Heap (Running time - $\mathcal{O}(n)$).
  2. Remove root element and heapify (maintain heap) ( Running time - $\mathcal{O}(\log{}n)$).
  3. Repeat above two steps for $k$ times.
  4. Return removed root element at $k$th step.

Total Running time : $\mathcal{O}(k \log \ n + k n )$

$\endgroup$
0
$\begingroup$

There is another different way to find k-th largest in an array.
Use Cartesian Tree, build Cartesian tree using array index and not keys. To search start from root, whose position you know, you can decide whether to move left sub-tree or right tree
If you are moving right sub-tree you have to search for k-root_index in right sub-tree
Check https://habrahabr.ru/post/102006/ for details

$\endgroup$
0
$\begingroup$

A binary heap will insert and remove minimum in $\mathcal{O}(\log{}n)$

  1. Inset the first K elements into a binary heap
  2. Starting at K+1 to n compare the element in the input array to the minimum in the binary heap
    If > minimum then remove the minimum from the binary heap and insert the element in the binary heap

I think it is order $\mathcal{O}(n \log{}k)$

for(int i = 0; i < input.count; i++)
    if(i < k)
       BinaryHeap.Add(input[i])
    else if (input[i] > BinaryHeap.min)
       BinaryHeap.Add(input[i]) 
       BinaryHeap.Remove(BinaryHeap.min)

return BinaryHeap.min
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.