黑箱子，穿梭千年的超时

黑箱子，穿越千年的超时
有一个黑箱子，里面会按升序存储整数，你可以对黑箱子下达下面的指令：
a. ADD n 将n加入黑箱子
b. Get 获得一个数，这个数在黑箱子里的序号（从0开始计数）是Get的出现次数。
黑箱子中最初存了一个数0，现给你一个操作序列，要你输出Get命令时获的那个数。


输入：

每行是一个命令，如果命令是”ADD”，则后面空一格，有一个整数。输入时保证GET命令不会越界


输出：

每行输出一个整数，整数为对应Get获得值。
 
Sample Input

ADD 3
GET
ADD 1
GET
ADD -4
ADD 2
ADD 8
GET
GET
ADD -1000
ADD 2
GET

 
Sample Output

3
3
2
3
2

//Time limit Exceed

#include <stdio.h>

#include <stdlib.h>

#define N 1000000

int MinHeap[N],minsize;

int MaxHeap[N],maxsize=1;

int minHeapPop()

{

    //用temp保存被弹出的元素，val保存最后一个待调整元素，h找到val应放置的位置,child为孩子位置

    int temp=MinHeap[1],val,h,child;

    val=MinHeap[minsize--];

    for(h=1,child=2*h; child<=minsize&&(val>MinHeap[child]||val>MinHeap[child+1]) ;){

        if(MinHeap[child+1]<MinHeap[child]){

            child++;

        }

        MinHeap[h]=MinHeap[child];

        h=child,child=2*h;

    }

    MinHeap[h]=val;

    return temp;

}

int maxHeapPop()

{

    int temp=MaxHeap[1],val,h,child;

    val=MaxHeap[maxsize--];

    for(h=1,child=2*h; child<=maxsize&&(val<MaxHeap[child]||val<MaxHeap[child+1]) ;){

        if(MaxHeap[child+1]>MaxHeap[child]){

            child++;

        }

        MaxHeap[h]=MaxHeap[child];

        h=child,child=2*h;

    }

    MaxHeap[h]=val;

    return temp;

}

void minHeapInsert(int x)

{

    int h=++minsize,parent=h/2;

    while(h>1 && x<MinHeap[parent]){

        MinHeap[h]=MinHeap[parent];

        h=parent,parent=h/2;

    }

    MinHeap[h]=x;

}

void maxHeapInsert(int x)

{

    int h=++maxsize,parent=h/2;

    while(h>1 && x>MaxHeap[parent]){

        MaxHeap[h]=MaxHeap[parent];

        h=parent,parent=h/2;

    }

    MaxHeap[h]=x;

}

void blackBoxOpera()

{

    char cmd[5];

    int x;

    while(scanf("%s",cmd)){

        if(cmd[0]=='G'){//the MinHeap's top element always is the answer

            printf("%d\n",MinHeap[1]);

            maxHeapInsert(minHeapPop());

        }

        else{

            scanf("%d",&x);

            if(x<MaxHeap[1]){//the MaxHeap's top is next "GET" position

                minHeapInsert(maxHeapPop());

                maxHeapInsert(x);

            }

            else

                minHeapInsert(x);

        }//else

    }//while

}

int main()

{

    blackBoxOpera();

    return 0;

}

最开始用双向链表做的，以为可以。果断超时。花了些时间搞这个堆，还是不行吖？
------解决方案--------------------
那就试试Splay Tree
------解决方案--------------------
不知道B树，行不？
------解决方案--------------------
B树可以吗？你可以试试吧，下面的代码可以参考下。

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>


/* Balance flag */

#define RH 1

#define LH -1

#define BH 0


static int lev_m=0;


typedef struct avlNode{

	int data;

	int balance;

	int level;

	struct avlNode *right;

	struct avlNode *left;

}*PavlNode;


void lltree(PavlNode *node)