#include <cstdio>
#include <cstring>

#define MAX_NUM_QUEUES 1000

// Struktura osoby. Alokujeme ji jen jednu, ostatni jsou odkazy.

struct Person {
        int IQ;
        char *Name;
        Person (int newIQ, char *newName) {
                IQ = newIQ;
                Name = strdup(newName);
        }
};

#define SWAP(A, B) do {  \
        Person *Tmp = A; \
        A = B;           \
        B = Tmp;         \
} while (0)

// struktura jednoho vrcholu v halde
struct Node {
        Node *Left, *Right;
        Person *P;
};


struct Queue {
        Node Root;
        int Size;
} Queue[MAX_NUM_QUEUES];

int Queues = 2;

// najde nejvetsi prvek - ten je vzdy ve vrcholu haldy
char *
find_best(int ID)
{
        return Queue[ID].Root.P->Name;
}

// odebere koren z haldy
int
delete_best (int ID)
{
        Queue[Queues].Size = Queue[ID].Size - 1;
        Node *Root;
        Node *A = &Queue[ID].Root;
        Node *B = &Queue[Queues].Root;
        int Pos = Queue[ID].Size;
        int log = 0;
        while (Pos >> log)
                log++;

        /* Pujdeme po strome dolu, smerem k poslednimu prvku (Pos), a
           budeme prvky posunovat nahoru */

        *B = *A;
        for (int i = log - 2; i > 0; i--) {
                if ((Pos >> i) & 1) {
                        puts ("right");
                        B->Right = new Node;
                        A = A->Right;
                        B = B->Right;
                } else {
                        puts ("left");
                        B->Left = new Node;
                        A = A->Left;
                        B = B->Left;
                }
                *B = *A;
        }
        Root = &Queue[Queues].Root;

        /* presunout nejpravejsi prvek v dolni hladine do vrcholu */

        if (Pos & 1) {
                Root->P = B->Right->P;
                B->Right = NULL;
        } else {
                Root->P = B->Left->P;
                B->Left = NULL;
        }

        /* bublat dolu a zabezpecit invariant IQ rodice > IQ synu */

        A = Root;
        while (1) {
                Node *Left = A->Left;
                Node *Right = A->Right;
                if (Right != NULL && Right->P->IQ > Left->P->IQ) {
                        if (Right->P->IQ > A->P->IQ) {
                                A->Right = new Node;
                                *(A->Right) = *Right;
                                SWAP(A->P, A->Right->P);
                                A = A->Right;
                        } else
                                break;
                }
                else if (Left != NULL) {
                        if (Left->P->IQ > A->P->IQ) {
                                A->Left = new Node;
                                *(A->Left) = *Left;
                                SWAP(A->P, A->Left->P);
                                A = A->Left;
                        }
                        else
                                break;
                }
                else
                        break;
        }
        return Queues++;
}

// vlozi prvek do haldy
int
insert (int ID, int IQ, char *Name)
{
        Queue[Queues].Size = Queue[ID].Size + 1;
        Node *A = &Queue[ID].Root;
        Node *B = &Queue[Queues].Root;
        int Pos = Queue[Queues].Size;
        int log = 0;
        while (Pos >> log)
                log++;

        /* odkazy na vrcholy na ceste k nejpravejsimu vrcholu ve
           spodni vrstve */

        Node *Path[log];
        Path[log - 1] = B;

        /* Sejdeme po strome smerem dolu k nejpravejsimu vrcholu */

        for (int i = log - 2; i >= 0; i--) {
                *B = *A;
                if ((Pos >> i) & 1) {
                        B->Right = new Node;
                        if (i)
                                A = A->Right;
                        B = B->Right;
                } else {
                        B->Left = new Node;
                        if (i)
                                A = A->Left;
                        B = B->Left;
                }
                Path[i] = B;
        }

        // pridat novy vrchol

        B->Left = B->Right = NULL;
        B->P = new Person (IQ, Name);

        // vybublat nahoru a zabezpecit rovnovahu

        for (int i = 0; i < log - 1; i++)
                if (Path[i]->P->IQ > Path[i + 1]->P->IQ)
                        SWAP(Path[i]->P, Path[i + 1]->P);
        return Queues++;
}

int
main(void)
{
        Queue[1].Size = 1;
        Queue[1].Root.P = new Person (0, "UNDERFLOW");
        insert(1, 130, "Ales");
        insert(2, 110, "Petr");
        insert(1, 140, "Jana");
        printf("%s\n", find_best(2));
        printf("%s\n", find_best(3));
        printf("%s\n", find_best(4));
        delete_best(3);
        printf("%s\n", find_best(5));
        return 0;
}