Minimum number of comparisons to find $2$nd smallest element

Question

Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$ comparisons in the worst case. (Hint: Also find the smallest element.) [1]

I tried but I have no idea how to, e.g. the best I could do is

//assume n>=2
//A: array of size n 
//returns second smallest in A 
//0 indexing in C++

int second_smallest(int*A,int n){
    queue<int> q;//always keep the size to 2 by push & pop. Also it stores indices. 
    q.push(1);//2nd smallest 
    q.push(0);//smallest
    for(int i=1;i<n;++i){
        if(A[i]<A[q.back()]){
            q.push(i);
            q.pop();
        }
    }
    int i=q.back()+1;//we know for sure A[0],...,A[q.back()-1] are greater than A[q.front()]. And A[q.back()] is the smallest.
    q.push(q.front());//after this line, assume q.back() is 2nd smallest 
    q.pop(); 
    for(;i<n;++i){
        if(A[i]<A[q.back()]){
            q.push(i);
            q.pop();
        }
    }
    return A[q.back()]; 
}

which conducts $(n-1)+(n-2)=2n-3$ comparisons in worst case. When input is uniformly distributed over all permutation the average number of comparisons is $(n-1)+n-E[q.back()]=\frac{3}{2}n-\frac{1}{2}$ where $q.back()$ refers to the one at $(*)$, and we know $E[q.back()]=\frac{1}{n}(1+...+n)=(n-1)/2$.

But this's no where near $n+\lceil\lg n\rceil-2$ so I'm out of idea could someone help?

[1] Introduction to Algorithms,MIT

Answer 1

Assume that all elements are distinct (if not, replace each element with a pair $(element, position)$ and perform the comparisons lexicographically) and consider a rooted binary tree $T$ with $n$ leaves in which each vertex has either $0$ or two children and every level, except possibly the last, is completely filled. Arbitrarily associate each leaf of $T$ with a distinct input element.

You can find the minimum by computing, for each interval vertex $v$, the minimum among all the elements associated to the leaves of the subtree of $T$ rooted at $v$. This can be done by performing a postorder visit of $T$: whenever $v$ is visited, let $v_\ell$ and $v_r$ be its two children, compare the elements associated with $v_\ell$ and $v_r$ and let the minimum among the two be the winner; the element associated with $v$ is exactly such winner.

At the end of the visit, the root of the tree will be associated with the minimum element of the input sequence.

Consider now the set $P$ of the vertices that have been associated with the minimum element and notice that they induce a root-to-leaf path in $T$. Let $C(P)$ denote the set of all children of the vertices in $P$. Since the second-smallest element $x$ can only lose against the minimum element, there must be a vertex associated with $x$ among those in $C(P) \setminus P$ (and this set contains no vertex associated with the minimum element). Then, you find the second-minimum of the input sequence be looking for the minimum of the elements associated with the vertices in $C(P) \setminus P$.

The overall number of comparisons is given by the sum of 1) the number of comparisons used to find the minimum, and 2) the number of comparisons needed to handle $C(P) \setminus P$. Regarding 1), we perform exactly $1$ comparison for each internal vertex, for a total of $n-1$ comparisons. Regarding 2), we perform $|C(P) \setminus P| - 1$ comparisons, where $|C(P) \setminus P|$ is at most the depth of $T$, i.e., $|C(P) \setminus P| \le \lceil \log n \rceil$. Then: $$ (n-1) + (|C(P) \setminus P|-1) \le (n-1) + (\lceil \log n \rceil - 1) = n + \lceil \log n \rceil - 2. $$

The above is this is just a handy description for the analysis of the number of comparison. You don't actually need to build and traverse the tree $T$. Here is a possible recursive implementation:

Input: a non-empty list L of distinct elements
Output: the second-minimum in L
Second-Minimum(L):
    (x, S) = Find-Candidates(L)
    Return the minimum in S

Input: a non-empty list L of distinct elements
Output: a pair (x, S), where x is the minimum in L, and S is a set of candidate second-minimum elements
Find-Candidates(L):
    If |L|==1:
        return (x, {}), where x is the only element in L

    Split L into L' and L'' with | |L'| - |L''| | <= 1
    (x', S') = Find-Candidates(L')
    (x'', S'') = Find-Candidates(L'')

    If x' < x'':
        Return (x', S' U {x''})
    Else:
        Return (x'', S'' U {x'})

Answer 2

Based on Steven's great answer, and some modification so that the second minimum is computed "on the fly" (this won't change the number of comparison) below implemented the algorithms in C++ that also prints the tree for visualization

e.g. with input array L = 3,1,5,2,4 the second smallest is 2 and the tree is printed after $90$ degree rotation to the right

                4
        2
                2
1
                5
        1
                        1
                1
                        3

code:

#include <iostream>
#include <stack>
using namespace std;
//declare only 
int*Find_Candidates(int*L,int p,int r,int*&winner,stack<int*>&post_order);
void print_in_order(stack<int*>&post_order,int depth);

//L is continuous array starting from indices p to r inclusive
//returns Second Minimum ie. smallest loser (second min) to winner (min)
int*Second_Minimum(int*L,int p,int r){
    int*winner=nullptr;
    stack<int*>post_order;
    int*second_minimum=Find_Candidates(L,p,r,winner,post_order);
    print_in_order(post_order,0);
    return second_minimum; 
}

//post_order is solely for printing purpose
//returns pointer to second minimum or nullptr if it doesn't exist
int*Find_Candidates(int*L,int p,int r,int*&winner,stack<int*>&post_order){
    //a single element must be winner
    if(p==r){
        winner=L+p; 
        post_order.push(nullptr);//left child
        post_order.push(nullptr);//right child
        post_order.push(winner);//this node
        return nullptr;//no one lost to the winner 
    }
    int q=(p+r)/2; //same as floor((p+r)/2), aka lower median
    int*lt_smallest_loser=Find_Candidates(L,p,q,winner,post_order); //smallest loser to winner in left subtree
    int*lt_winner=winner; //winner from left subtree 
    int*rt_smallest_loser=Find_Candidates(L,q+1,r,winner,post_order); //smallest loser to winner in right subtree
    int*rt_winner=winner; //winner from right subtree 

    if(*lt_winner<*rt_winner){
        winner=lt_winner;//rt_winner becomes a loser now 
        post_order.push(winner);
        if(lt_smallest_loser!=nullptr&&
            *lt_smallest_loser<*rt_winner){
            return lt_smallest_loser;// still the smallest loser 
        }else
            return rt_winner;// rt_winner becomes the smallest loser 
    }else{
        winner=rt_winner;//lt_winner becomes a loser now 
        post_order.push(winner);
        if(rt_smallest_loser!=nullptr&&
            *rt_smallest_loser<*lt_winner){
            return rt_smallest_loser;// still the smallest loser 
        }else
            return lt_winner;// lt_winner becomes the smallest loser 
    }
}

void print_in_order(stack<int*>&post_order,int depth){
    int*root=post_order.top(); 
    post_order.pop();
    if(root==nullptr)
        return; 
    else{
        //print right
        print_in_order(post_order,depth+1);
        for(int i=0;i<depth;++i)
            cout<<'\t';//print tab
        cout<<*root<<endl;
        //print left
        print_in_order(post_order,depth+1);
    }
}

int main(){
    int L[]{3,1,5,2,4};
    int n=sizeof(L)/sizeof(int);
    int*result=Second_Minimum(L,0,n-1); 
    cout<<"2nd smallest: "; 
    if(result!=nullptr)
        cout<<*result<<endl;
    else
        cout<<"doesn't exist"<<endl;
}