算法导论 9.1-1 求第二小元素

我就是我 2022-05-14 11:36 116阅读 0赞

# 一、题目 #

证明：在最坏情况下，利用n+ceil(lgn)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素）

# 二、思考 #

step1：对所有元素，两个一组比较大小，小的一个进入下一轮比较。一直到比较出最小的元素。此时所有比较结果构成一棵二叉树。比较次数为n-1。

![1347765718_1302.gif][]

step2：沿着树从树根向下到叶子，找出第二小的元素，比较次数是ceil\[lgn\]-1。令m2\[p\]表示以p为根的树中的第二小元素。对于当前处理结点为p，key\[p\] = min\{key\[left\[p\]\], key\[right\[p\]\]\}。假设key\[p\] =  key\[left\[p\]\]，则m2\[p\] = min\{m2\[left\[p\]\], key\[right\[p\]\]\}

![1347765776_8709.gif][]

# 三、代码 #

#include <iostream>
    using namespace std;
    //第一遍求最小值的结果用树表示
    struct node
    {
    	int key;
    	node *next;//指向同一层中的下一个元素
    	node *p;
    	node *left;
    	node *right;
    	node(int k):key(k),next(NULL),p(NULL),left(NULL),right(NULL){}
    };
    //求第二小值
    int Find_S2(node *head)
    {
    	node *p, *q, *r, *t;
    	//step1：求最小值
    	//两两比较，较小的一个进入下一轮，这个循环当只剩下一个元素时结束
    	while(head->next != NULL)
    	{
    		//从第一个元素开始，head指向比完后较小的那一组数据中的第一个
    		p = head;head = NULL;
    		while(p)
    		{
    			//如果这组数据有奇数个，最后一个元素直接晋级
    			if(p->next == NULL)
    			{
    				r = new node(p->key);
    				r->left = p;
    				p->p = r;
    				p = p->next;
    			}
    			//p与p->next比较，较小的元素晋级
    			else
    			{
    				q = p->next;
    				r = new node(min(p->key, q->key));
    				r->left = p;
    				r->right = q;
    				p->p = r;
    				q->p = r;
    				p = q->next;
    			}
    			//head指向比完后较小的那一组数据中的第一个，t用于把head指向的数据链成链表
    			if(head == NULL)
    			{
    				head = r;
    				t=  head;
    			}
    			else
    			{
    				t->next = r;
    				t = r;
    			}
    		}
    	}
    	//step2：求最第二小值
    	//Min用于存储最小值，Min2用于存储第二小值
    	int Min = head->key, Min2 = 0x7fffffff;
    	//从根结点向下比较
    	p = head;
    	//比较到叶子结点时循环结束
    	while(p->left != NULL)
    	{
    		//当前结点的值来源于右孩子
    		if(p->right && p->right->key == Min)
    		{
    			Min2 = min(Min2, p->left->key);
    			p = p->right;
    		}
    		//当前结点的值来源于左孩子
    		else
    		{
    			//由左孩子直接晋级的情况
    			if(p->right)
    				Min2 = min(Min2, p->right->key);
    			p = p->left;
    		}
    	}
    	return Min2;
    }
    //测试
    int main()
    {
    	int A[8] = {0};
    	node *head = NULL;
    	//生成8个随机测试数据
    	for(int i = 0; i < 8;i++)
    	{
    		A[i] = rand() % 100;
    		//构造成树的最底层结点
    		node *p = new node(A[i]);
    		p->next = head;
    		head = p;
    	}
    	//运行算法并输出结果
    	cout<<Find_S2(head)<<endl;
    	return 0;
    }

转载自： [http://blog.csdn.net/mishifangxiangdefeng/article/details/7983809][http_blog.csdn.net_mishifangxiangdefeng_article_details_7983809]

[1347765718_1302.gif]: https://img-my.csdn.net/uploads/201209/16/1347765718_1302.gif
[1347765776_8709.gif]: https://img-my.csdn.net/uploads/201209/16/1347765776_8709.gif
[http_blog.csdn.net_mishifangxiangdefeng_article_details_7983809]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7983809