题解 | #【模板】堆#

【模板】堆

https://www.nowcoder.com/practice/13f61c8c92404f5ea5d6fa4c692869fb

#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;
}

全部评论

相关推荐

群星之怒:1.照片可以换更好一点的,可以适量P图,带一些发型,遮住额头,最好穿的正式一点,可以适当P图。2.内容太少。建议添加的:求职意向(随着投递岗位动态更改);项目经历(内容太少了建议添加一些说明,技术栈:用到了什么技术,还有你是怎么实现的,比如如何确保数据传输稳定的,角色注册用到了什么技术等等。)项目经历是大头,没有实习是硬伤,如果项目经理不突出的话基本很难过简历筛。3.有些内容不必要,比如自我评价,校内实践。如果实践和工作无关千万别写,不如多丰富丰富项目。4.排版建议:建议排版是先基础信息,然后教育背景(要突出和工作相关的课程),然后专业技能(一定要简短,不要长篇大论,写你会什么,会的程度就可以),然后是项目经历(一定要详细,占整个简历一定要超过一半,甚至超过百分之70都可以)。最后如果有一部分空白的话可以填补上校内获得的专业相关的奖项,没有就写点校园经历和自我评价。5.技术一定要够硬,禁得住拷打。还有作息尽量保证正常,不要太焦虑。我24双非本科还是非科班,秋招春招各找了一段实习结果都没有转正,当时都想噶了,最后6月份在校的尾巴也找到一份工作干到现在,找工作有时很看运气的不要急着自我否定。 加油
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务