题解 | #【模板】堆#

#include <stdio.h>

#define MAX_SIZE 100005 // 最大堆的大小

// 定义大根堆的数组和大小
int heap[MAX_SIZE], size = 0;

// 交换两个整数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 插入操作（push）
// 将一个整数 x 插入堆中，并通过上滤操作保持大根堆性质
void push(int x) {
    // 将新元素插入堆的最后一个位置
    heap[++size] = x;
    // 上滤操作，将新元素调整到合适的位置
    for (int i = size; i > 1 && heap[i] > heap[i / 2]; i /= 2) {
        swap(&heap[i], &heap[i / 2]);
    }
}

// 堆顶操作（top）
// 输出堆顶元素
void top() {
    // 如果堆为空，输出 "empty"
    if (size == 0) {
        printf("empty\n");
    } else {
        // 输出堆顶元素
        printf("%d\n", heap[1]);
    }
}

// 弹出操作（pop）
// 输出堆顶元素，并从堆中删除堆顶元素
void pop() {
    // 如果堆为空，输出 "empty"
    if (size == 0) {
        printf("empty\n");
    } else {
        // 输出堆顶元素
        printf("%d\n", heap[1]);
        // 将堆顶元素替换为堆的最后一个元素，并减少堆的大小
        heap[1] = heap[size--];
        // 下滤操作，将堆顶元素调整到合适的位置
        for (int i = 1, maxChild; (i * 2) <= size; i = maxChild) {
            maxChild = i * 2; // 左孩子
            // 如果右孩子存在且大于左孩子，则选择右孩子
            if (maxChild < size && heap[maxChild + 1] > heap[maxChild]) {
                maxChild++;
            }
            // 如果堆顶元素小于最大的孩子，则交换
            if (heap[i] < heap[maxChild]) {
                swap(&heap[i], &heap[maxChild]);
            } else {
                break;
            }
        }
    }
}

// 主函数
int main() {
    int n, x;
    char op[10];
    // 读取操作次数
    scanf("%d", &n);
    // 循环读取并执行操作
    while (n--) {
        // 读取操作字符串
        scanf("%s", op);
        // 如果操作是 "push"
        if (strcmp(op, "push") == 0) {
            // 读取要插入的整数 x
            scanf("%d", &x);
            // 执行插入操作
            push(x);
        } else if (strcmp(op, "pop") == 0) {
            // 如果操作是 "pop"，执行弹出操作
            pop();
        } else if (strcmp(op, "top") == 0) {
            // 如果操作是 "top"，执行堆顶操作
            top();
        }
    }
    return 0;
}