/*
    「節点のキーがその親のキー以下である」という max-ヒープ条件を満たすヒープを、max-ヒープと呼びます。
    max-ヒープでは、最大の要素が根に格納され、ある節点を根とする部分木の節点のキーは、その部分木の根のキー以下となります。
    親子間のみに大小関係があり、兄弟間に制約はないことに注意してください。

    与えられた配列から以下の疑似コードに従ってmax-ヒープを構築するプログラムを作成してください。

    maxHeapify(A,i) は、節点 i を根とする部分木が max-ヒープになるよう A[i] の値を max-ヒープの葉へ向かって下降させます。ここで H をヒープサイズとします。
    次の buildMaxHeap(A) はボトムアップに maxHeapify を適用することで配列 A を max-ヒープに変換します。

    入力：入力の最初の行に、ヒープのサイズ H が与えられます。
    　　　続いて、ヒープの節点の値を表す H 個の整数が節点の番号が 1 から H に向かって順番に空白区切りで与えられます。
    
    出力：max-ヒープの節点の値を節点の番号が 1 から H に向かって順番に１行に出力してください。
    　　　各値の直前に１つの空白文字を出力してください。
    
    制約：1≤H≤500,000
    　　　−2,000,000,000≤節点の値≤2,000,000,000
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define SWAP(type, a, b) do { type t = a; a = b; b = t; } while(0)

#ifdef DEBUG
    #define DEBUG_WRITE(...) fprintf(stderr, __VA_ARGS__)
#else
    #define DEBUG_WRITE
#endif

#define HEAP_SIZE_MAX 10000000

typedef struct {
    int *node;
    int size;
} Heap;

int getParent(int idx);
int getLeft(int idx);
int getRight(int idx);
bool isCorrectHeapIdx(int idx, int heapSize);
bool initialize(Heap *heap);
void maxHeapify(Heap *heap, int idx);
void buildMaxHeap(Heap *heap);
void printHeap(Heap *heap);
void terminate(Heap *heap);

int getParent(int idx) {
    return idx / 2;
}

int getLeft(int idx) {
    return idx * 2;
}

int getRight(int idx) {
    return idx * 2 + 1;
}

bool isCorrectHeapIdx(int idx, int heapSize) {
    return idx <= heapSize && 1 <= idx;
}

bool initialize(Heap *heap) {
    if((heap->node = malloc((HEAP_SIZE_MAX + 1) * sizeof(int))) == NULL) {
        return false;
    }

    heap->size = 0;
    return true;
}

void maxHeapify(Heap *heap, int idx) {
    int left = getLeft(idx);
    int right = getRight(idx);

    int maxIdx = idx;
    if(isCorrectHeapIdx(left, heap->size) && heap->node[maxIdx] < heap->node[left]) {
        maxIdx = left;
    } if(isCorrectHeapIdx(right, heap->size) && heap->node[maxIdx] < heap->node[right]) {
        maxIdx = right;
    }

    if(maxIdx != idx) {
        SWAP(int, heap->node[maxIdx], heap->node[idx]);
        maxHeapify(heap, maxIdx);
    }
}

void buildMaxHeap(Heap *heap) {
    for(int i = getParent(heap->size); i >= 1; i--) {
        maxHeapify(heap, i);
    }
}

void printHeap(Heap *heap) {
    for(int i = 1; i <= heap->size; i++) {
        printf(" %d", heap->node[i]);        
    }
    puts("");
}

void terminate(Heap *heap) {
    free(heap->node);
    heap->node = NULL;
    heap->size = 0;
}

bool isFull(Heap *heap) {
    return heap->size >= HEAP_SIZE_MAX;
}

bool isEmpty(Heap *heap) {
    return heap->size <= 0;
}

bool insert(Heap *heap, int key) {
    if(isFull(heap)) {
        printf("!");
        return false;
    }

    heap->node[++heap->size] = key;
    for(int i = getParent(heap->size); i >= 1; i = getParent(i)) {
        maxHeapify(heap, i);
    }

    return true;
}

bool extract(Heap *heap, int *key) {
    if(isEmpty(heap)) {
        return false;
    }

    *key = heap->node[1];
    heap->node[1] = heap->node[heap->size--];
    maxHeapify(heap, 1);

    return true;
}

int main(void) {
    Heap heap;

    initialize(&heap);

    int extractValue[HEAP_SIZE_MAX];
    int extractCnt = 0;

    char buf[32];
    while(1) {
        fgets(buf, sizeof(buf), stdin);
        if(!strncmp(buf, "en", 2)) {
            break;
        }
            char command[16];
            int key;
        if(buf[0] == 'i') {
            sscanf(buf, "%s %d", command, &key);
            insert(&heap, key);
        } else if(buf[0] == 'e') {
            extract(&heap, &key);
            printf("%d\n", key);
            // extract(&heap, &extractValue[extractCnt++]);
        }
    }

    /*
    for(int i = 0; i < extractCnt; i++) {
        printf("%d\n", extractValue[i]);
    }
    */

    terminate(&heap);
    return 0;
}


Measured memory_bytes: 5456