How to find the kth minimum element from a Double linked list?

Question

I need to implement a function which can be find the kth minimum from doubly linked list.

I searched on internet and come to know about this :

• quickSelect logic and k-th order statistic algorithm would be effective for array or vector but here i am using linked list where I do not have any size of linked list so its hard to divide them in 5 elements part.

My function testcase is looks like this :

for(int i = 0; i < 1000; ++i)
{
    // create linked list with 1000 elements
    int kthMinimum = findKthMin(LinkedList, i);
    // validate kthMinimum answer.
}

Here linkedlist can be in anyorder, we have to assume randomized only.

Any idea or suggestion to find kth minimum from doubly linked list in efficient time?

Thanks

Answer 1

If the list is doubly-linked, you can run the QuickSort algorithm on it. On my experience QuickSort is the fastest sorting algorithm (measured generating random lists, and pitting it against HeapSort and MergeSort). After that, simply walk the list k-positions to get your k-th smallest element.

QuickSort average time is O(n*log(n)), walking the list will be O(k), which in its worst case is O(n). So, total time is O(n*log(n)).

Answer 2

Algorithm

You can maintain a heap of size k by doing the following:

1. Fill the array with the k first elements of the list.
2. Heapify the array (using a MaxHeap)
3. Process the remaining elements of the list:
   • If top of the heap (the max) is greater than the current element in the list e, replace it with e (and maintain the heap invariant)
   • If the element is greater, just ignore it and carry on

At the end of the algorithm, the k-th smallest element will be at the top of the heap.

Complexity

Accumulate the first k elements + heapify the array: O(k)
Process the remaining part of the list O((n-k)ln(k)).