为方便处理，设输入规模n为2的次方。
算法：将数组划分成对，比较选出最小的元素，这些选出的最小元素再次划分成对，再比较选出最小元素，重复这个过程，直到找出整个数组的最小元素。这个过程是一个自底向上构造二叉树的过程，在构造的过程中记录最小元素的生成路径，回溯路径上的兄弟结点即可找出第二小的元素。
构造二叉树找出最小元素比较n-1次，回溯找出第二小元素比较lgn -1次，所以总共比较n+lgn-2次。
#include <iostream>
#include <vector>
struct Node
{
int key;
std::size_t prev; // 上一层的结点索引
Node(int x, int i) : key(x), prev(i) {}
};
std::size_t getsecond(const std::vector<Node> &floor, int &second)
{
if (floor.size() == 1)
return floor.front().prev;
std::vector<Node> nextFloor;
for (std::size_t i = 0; i < floor.size(); i += 2)
{
if (floor[i].key < floor[i+1].key) // 生成二叉树找出最小元素的比较
nextFloor.emplace_back(floor[i].key, i);
else
nextFloor.emplace_back(floor[i+1].key, i+1);
}
std::size_t path = getsecond(nextFloor, second); // 最小元素的路径索引
std::size_t other = path / 2 * 2 + ((path + 1) % 2); // 最小元素的兄弟索引
second = floor[other].key < second ? floor[other].key : second; // 递归回溯找出第二小元素的比较
return path;
}
int main()
{
int a[] = {1, 8, 3, 4, 5, 6, 7, 2};
std::vector<Node> nodes;
for (int t: a)
nodes.emplace_back(t, -1);
int second = 0x7fffffff;
getsecond(nodes, second);
std::cout << "second smallest: " << second << std::endl;
return 0;
}
