算法导论9.1-1例题:
证明:在最坏情况下,利用次比较,即可得到n个元素中的第2小元素。(提示:同时找最小元素)
这道题可以用胜者树去解决,具体的答案可以参考一下这里,我就不再细说,主要说一下胜者树与败者树,这里我贴一下胜者树的代码:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct queue
{
int start;
int end;
int *data;
} Queue;
void init(Queue* tree,int* A);
void insert(Queue* tree,int data);
int getnum(Queue* tree);
bool isEmpty(Queue* tree);
int main(void)
{
int A[10]={12,567,456,120,54,30,32,545,129,65};
Queue* tree=(Queue*)malloc(sizeof(Queue));
init(tree,A); //tree为队列,命名时脑子抽了,手动滑稽
int successtree[10]={0};
for(int j=9;j>=0&&(!isEmpty(tree));j--)
{
int x=getnum(tree);
int y=getnum(tree);
if(x>y)
{
successtree[j]=x;
insert(tree,x);
}
else
{
successtree[j]=y;
insert(tree,y);
}
}
for(int i=0;i<10;i++)
printf("%d ",successtree[i]);
return 0;
}
void init(Queue* tree,int* A)
{
tree->start=0;
tree->end=9;
tree->data=(int*)malloc(10*sizeof(int));
for(int i=0;i<10;i++)
tree->data[i]=A[i];
}
void insert(Queue* tree,int data)
{
if(tree->end!=9)
{
tree->data[tree->end+1]=data;
tree->end++;
}
else
{
tree->end=0;
tree->data[tree->end]=data;
}
}
int getnum(Queue* tree)
{
if(tree->start!=9)
{
tree->start++;
return tree->data[tree->start-1];
}
else
{
tree->start=0;
return tree->data[9];
}
}
bool isEmpty(Queue* tree)
{
if(tree->start==tree->end)
return true;
else
return false;
}
胜者树的构建与堆类似,都是一颗完全二叉树,不同于堆的是,胜者树要求我们从下往上构建,这里可以联想到Huffman Tree的构建方法,我们都知道Huffman Tree是利用优先队列(堆)构建的,这里呢,胜者树只要用普通的队列即可
败者树与胜者树不一样的地方在于,胜者树的中间结点记录的是胜者的标号;而败者树的中间结点记录的败者的标号。二者可以在的时间内找到最值,关于败者树,胜者树孰优孰劣的问题,可以参考一下这里。
,胜者树在节点上升的时候首选需要获得父节点,然后再获得兄弟节点,然后再比较。这时人们又想能否再次减少比较次数,于是就有了败者树,在使用败者树的时候,每个新元素上升时,只需要获得父节点并比较即可。所以总的来说,减少了访存的时间。现在程序的主要瓶颈在于访存了,计算倒几乎可以忽略不计了。