算法导论笔记：胜者树与败者树 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是利用优先队列（堆）构建的，这里呢，胜者树只要用普通的队列即可

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