算法导论笔记:胜者树与败者树 9.1-1

算法导论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是利用优先队列(堆)构建的,这里呢,胜者树只要用普通的队列即可

败者树与胜者树不一样的地方在于,胜者树的中间结点记录的是胜者的标号;而败者树的中间结点记录的败者的标号。二者可以在的时间内找到最值,关于败者树,胜者树孰优孰劣的问题,可以参考一下这里
,胜者树在节点上升的时候首选需要获得父节点,然后再获得兄弟节点,然后再比较。这时人们又想能否再次减少比较次数,于是就有了败者树,在使用败者树的时候,每个新元素上升时,只需要获得父节点并比较即可。所以总的来说,减少了访存的时间。现在程序的主要瓶颈在于访存了,计算倒几乎可以忽略不计了。

发表评论