Blog # 33 : Second Minima
Find second smallest element in an array A[1..N] of size N. (We would like to do in much less than 2N comparisons if possible).
Solution:
I suppose the method to solve is mentioned in Cormen and it takes n + log(n) - 2 comparisons. (Tournament style with saving elements that lost to minima; then searching for second minima in them)
Similar method is using Heap data structure to do it in n + log(n) comparisons. (Build heap in n and Min heapify in log(n))
The question does not end here as the above solutions use comparisons to get 2nd and in general kth minima. We can use other methods without comparisons (at the cost of space) to get kth minima.
I thought of using Trie data structure to get it done easily. We simply assume the maximum digits in the elements in the array and padd them with 0's at the beginning to make them D digits large. We insert each into D level trie and the pre-order traversal gives all elements in correct sorted order.
Bucket sort, Radix sort are other possibilities. Try to learn about these methods.
Courtsey: Vibhaj
Solution:
I suppose the method to solve is mentioned in Cormen and it takes n + log(n) - 2 comparisons. (Tournament style with saving elements that lost to minima; then searching for second minima in them)
Similar method is using Heap data structure to do it in n + log(n) comparisons. (Build heap in n and Min heapify in log(n))
The question does not end here as the above solutions use comparisons to get 2nd and in general kth minima. We can use other methods without comparisons (at the cost of space) to get kth minima.
I thought of using Trie data structure to get it done easily. We simply assume the maximum digits in the elements in the array and padd them with 0's at the beginning to make them D digits large. We insert each into D level trie and the pre-order traversal gives all elements in correct sorted order.
Bucket sort, Radix sort are other possibilities. Try to learn about these methods.
Courtsey: Vibhaj
Posts
