题解 | #【模板】堆#

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

#define MAXLEN 100000



void up(int* heap, int top) {

    int temp;
    while (heap[top] > heap[(top - 1) / 2]) {
        temp = heap[top];
        heap[top] = heap[(top - 1) / 2];
        heap[(top - 1) / 2] = temp;
        top = (top - 1) / 2;
    }

}

void down(int* heap, int index, int heapSize) {
    int left = 2 * index + 1;
    int temp;

    while (left < heapSize) {
        // 寻找左子节点和右子节点的最大值，left+1 为右子节点，当右子节点存在且右子节点的值大于左子节点的值的时候，largest才是右子节点。
        int largest = left ;
        if((left + 1 < heapSize) && (heap[left + 1] > heap[left])) largest++;
        // 把左右子节点中的最大值和父节点进行比较，来判断是否进行交换
        largest = heap[largest] > heap[index] ? largest : index;
        // 如果当前节点比它的左右子节点都大的话，就没有必要再进行交换了。
        if (largest == index)  break;

        temp = heap[largest];
        heap[largest] = heap[index];
        heap[index] = temp;

        index = largest;
        left = index * 2 + 1;
    }
}
int main() {
    int n, top = 0;
    int a, len;
    char s[128];
    int stack[MAXLEN + 2];

    scanf("%d", &n);
    while (n--) {
        fgets(s, sizeof(s), stdin);
        if (s[0] == '\n') fgets(s, sizeof(s), stdin);

        if (s[1] == 'u') {
            a = 0;
            a = atoi(s + 5);
            stack[top++] = a;
            up(stack, top - 1);
        } else if (s[0] == 't') {
            if (top == 0)
                printf("empty\n");
            else printf("%d\n", stack[0]);
        } else {
            if (top == 0)
                printf("empty\n");
            else  {
                printf("%d\n", stack[0]);
                stack[0] = stack[--top];
                stack[top] = 0;
                down(stack, 0, top);
            }
        }
    }

    return 0;
}