L2-012关于堆的判断

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

#define MAX_SIZE 1000

int H[MAX_SIZE]; // 小顶堆，用于存储堆中的元素
int size = 0;    // 堆的当前大小，初始为 0

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

// 插入元素
void insert(int x) {
    if (size >= MAX_SIZE) return; // 如果堆已满，直接返回

    H[size] = x; // 将新元素放在数组末尾
    int i = size;
    size++;

    // 上浮操作，调整堆
    while (i > 0 && H[(i - 1) / 2] > H[i]) {
        swap(&H[(i - 1) / 2], &H[i]); // 如果父节点大于当前节点，交换
        i = (i - 1) / 2; // 继续向上调整
    }
}

// 查找节点的索引
int findIndex(int x) {
    for (int i = 0; i < size; i++) {
        if (H[i] == x) return i; // 如果找到节点，返回其索引
    }
    return -1; // 未找到节点，返回 -1
}

// 判断命题：x 是否是根节点
bool isRoot(int x) {
    return H[0] == x; // 根节点是堆的第一个元素
}

// 判断命题：x 和 y 是否是兄弟节点
bool areSiblings(int x, int y) {
    int idxX = findIndex(x); // 找到 x 的索引
    int idxY = findIndex(y); // 找到 y 的索引
    if (idxX == -1 || idxY == -1) return false; // 如果任一节点未找到，返回 false
    return (idxX - 1) / 2 == (idxY - 1) / 2; // 检查它们的父节点是否相同
}



// 判断命题：x 是否是 y 的子节点
bool isChild(int x, int y) {
    int idxX = findIndex(x); // 找到 x 的索引
    if (idxX == -1) return false; // 如果 x 未找到，返回 false
    return H[(idxX - 1) / 2] == y; // 检查 x 的父节点是否为 y
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M); // 读取插入元素的个数 N 和命题数 M

    // 插入元素
    for (int i = 0; i < N; i++) {
        int x;
        scanf("%d", &x); // 读取要插入的元素
        insert(x);       // 将元素插入堆
    }

    // 处理命题
    getchar(); // 消耗换行符，避免影响后续输入
    for (int i = 0; i < M; i++) {
        char prop[100];
        fgets(prop, sizeof(prop), stdin); // 读取整行输入（命题）

        if (strstr(prop, "is the root") != NULL) {
            // 如果命题是 "x is the root"
            int x;
            sscanf(prop, "%d", &x); // 提取 x 的值
            printf("%c\n", isRoot(x) ? 'T' : 'F'); // 判断并输出结果
        } else if (strstr(prop, "are siblings") != NULL) {
            // 如果命题是 "x and y are siblings"
            int x, y;
            sscanf(prop, "%d and %d", &x, &y); // 提取 x 和 y 的值
            printf("%c\n", areSiblings(x, y) ? 'T' : 'F'); // 判断并输出结果
        } else if (strstr(prop, "is the parent of") != NULL) {
            // 如果命题是 "x is the parent of y"
            int x, y;
            sscanf(prop, "%d is the parent of %d", &x, &y); // 提取 x 和 y 的值
            printf("%c\n", isParent(x, y) ? 'T' : 'F'); // 判断并输出结果
        } else if (strstr(prop, "is a child of") != NULL) {
            // 如果命题是 "x is a child of y"
            int x, y;
            sscanf(prop, "%d is a child of %d", &x, &y); // 提取 x 和 y 的值
            printf("%c\n", isChild(x, y) ? 'T' : 'F'); // 判断并输出结果
        }
    }

    return 0; // 程序正常结束
}