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?
$\begingroup$
$\endgroup$
1
-
$\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– Raphael2017-07-04 22:34:24 +00:00Commented Jul 4, 2017 at 22:34
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
You don't need to sort the list for finding $k$-th largest element. You can use Max Heap data structure .
Algorithm $(A,k)$
- Build Max-Heap (Running time - $\mathcal{O}(n)$).
- Remove root element and heapify (maintain heap) ( Running time - $\mathcal{O}(\log{}n)$).
- Repeat above two steps for $k$ times.
- Return removed root element at $k$th step.
Total Running time : $\mathcal{O}(k \log \ n + k n )$
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
A binary heap will insert and remove minimum in $\mathcal{O}(\log{}n)$
- Inset the first K elements into a binary heap
- 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
