CLRS 9.1.1 Finding Second Smallest Element

http://clrs.skanev.com/09/01/01.html

Show that the second smallest of n elements can be found with n+⌈lgn⌉−2 comparisons in the worst case. (Hint:Also find the smallest element.)

We can compare the elements in a tournament fashion - we split them into pairs, compare each pair and then proceed to compare the winners in the same fashion. We need to keep track of each "match" the potential winners have participated in.

We select a winner in n−1 matches. At this point, we know that the second smallest element is one of the lgn elements that lost to the smallest ­ each of them is smaller than the ones it has been compared to, prior to losing. In another ⌈lgn⌉−1 comparisons we can find the smallest element out of those. This is the answer we are looking for.

http://n1b-algo.blogspot.com/2008/12/finding-second-smallest-element.html
Finding the smallest element is trivial. The following code would find the smallest element using n-1 comparisons.

min = A[1]
for i = 2 to n
  if A[i] < min 
    min = A[i]
return min

The trivial algorithm to find the second minimum is to keep another variable (smin) along with min and if an element knocks out smin then check if it knocks out min and accordingly do the book-keeping. It can be done using 2n-3 comparisons and takes constant space. A point to observe is that the second smallest element is knocked out by the smallest one at some stage. If we preserve which element is knocked out by whom then finding the second smallest element would just require us to find the smallest amongst the elements knocked out by the smallest element. But in order to do that we need to build the algorithm in a way that we are playing a pair wise tournament. Lets say we play a tournament and knockout n/2 elements after n/2 comparisons. The recurrence relation looks like this:

T(n) = T(n/2) + n/2

Solving this recurrence gives that T(n) = n - 1. The height of the recurrence tree is lg n. So if we just check these elements knocked by root (min) we get the second minimum.For. E.x.

1   5 2   6  
\ /   \ /  
 1     2
  \   /
    1

As soon as we build the tree using n-1 comparisons, we can check the second largest amongst the number knocked out by 1. i.e. 2, 5. so the second minimum is 2. The number of comparison is n + ceil(log n) - 2, where log is taken to the base 2. We implement this algorithm by maintaining a list of indices knocked by an element. The python code is towards the end of this post. 

Another algorithm that is very easy to implement but sadly takes 2n - 2logn - 1 in terms of array element comparisons. Simply build a min heap (rooted at 1). Return the smaller of numbers at index 2 or 3 in the array. The cost of min heap building is = 2 * [n/4 + 2n/8 + ...... + (logn - 1) * n / 2^logn]. The solution to this arithmetic - geometric series is 2n - 2logn - 2. Comparing elements at 2nd and 3rd index adds one to the cost. Its very easy to implement though.
https://github.com/n1balgo/algo/blob/master/second_smallest.py

	# number of comparisons
	num_compare = 0
	# indexes that are to be compared
	idx = range(0,len(arr))
	# list of knockout for all elements
	knockout = [[] for i in idx]
	# play tournaments, until we have only one node left
	while len(idx) > 1:
	# index of nodes that win this tournament
	idx1 = []
	# nodes in idx odd, if yes then last automatically goes to next round
	odd = len(idx) % 2
	# iterate over even indexes, as we do a paired tournament
	for i in xrange(0, len(idx) - odd, 2):
	# first index
	i0 = idx[i]
	# second index
	i1 = idx[i+1]
	# update num comparisons
	num_compare += 1
	# perform tournament
	if arr[i0] < arr[i1]:
	# i0 qualifies for next round
	idx1.append(i0)
	# add arr[i1] to knockout list of i0
	knockout[i0].append(arr[i1])
	else:
	# i1 qualifies for next round
	idx1.append(i1)
	# add arr[i0] to knockout list of i1
	knockout[i1].append(arr[i0])
	# last element goes to next round
	if odd == 1:
	idx1.append(idx[i+2])
	# perform new tournament
	idx = idx1
	print "Smallest element =", arr[idx[0]]
	print "Total comparisons =", num_compare
	print "Nodes knocked off by the smallest =", knockout[idx[0]], "\n"
	# compute second smallest
	a = knockout[idx[0]]
	if len(a) > 0:
	v = a[0]
	for i in xrange(1,len(a)):
	num_compare += 1
	if v > a[i]: v = a[i]
	print "Second smallest element =", v
	print "Total comparisons =", num_compare

https://github.com/n1balgo/algo/blob/master/second_smallest_linkedlist.py
http://ripcrixalis.blog.com/2011/02/21/clrs-9-1-minimum-and-maximum/
https://github.com/gzc/CLRS/blob/master/C09-Medians-and-Order-Statistics/exercise_code/second-smallest.cpp