题解 | #【模板】堆#

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

//void print(int* h, int len){
//    // printf("\n");
//    for(int i=0; i< len; i++){
//        printf("%d ",h[i]);
//    }
//    printf("\n");
//}

void swap(int* h, int i, int j){
    // 交换
    int temp = h[i];
    h[i] = h[j];
    h[j] = temp;
}

void adjust_up(int *h, int len){
    // 向上调整大根堆，用于建堆；
    if(len > 1){
        for(int i = len-1; i>=0; i--){
            int father;
            if(i%2 == 0){
                father = (i-2)/2;
            }else{
                father = (i-1)/2;
            }
            if(father < 0){
                break;
            }
            if(h[i]>h[father]){
                swap(h, i, father);
            }
        }
    }
}
void adjust_down(int *h, int len){
    // 向下调整大根堆，用于调整堆；
    if(len > 1){
        for(int i = 0; i<len; i++){
            int son_l, son_r;
            son_l = i*2+1;
            son_r = i*2+2;
            if(son_l < len){
                if(h[i]<h[son_l]){
                    swap(h, i, son_l);
                }
                if(son_r < len){
                    if(h[i]<h[son_r]){
                        swap(h, i, son_r);
                    }
                }
            }else{
                break;
            }
        }
    }
}

void move0(int*h, int len){
    for(int i=len; i>0; i--){
        h[i] = h[i-1];
    }
}

void push_x(int *h, int len, int x){
    // x加入堆。保证x为int型整数,不输出任何内容
    // 建堆
    if(len == 0){
        h[0] = x;
    }else{
        if(x>h[0]){
            move0(h, len);
            h[0] = x;
        }else{
            h[len] = x;
            adjust_up(h, len+1);
        }
    }
}

void top(int *h, int len){
    // 输出堆顶元素。若堆为空，输出"empty"(不含引号)。
    if(len == 0){
        printf("empty\n");
    }else{
        printf("%d\n", h[0]);
    }
}

void pop(int *h, int len){
    top(h, len);
    if(len>1){
        // 输出堆顶元素，且弹出堆顶。若堆为空，输出"empty"(不含引号)
        swap(h, 0, len-1);
        // print(h, len-1);
        adjust_down(h, len-1);
        // print(h, len-1);
    }
}

int main() {
    int n;
    scanf("%d",&n);
    getchar();
    // 堆数组
    int heap[n];
    int num=0;
    for(int i=0; i<n; i++){
        char line[100];
        int line_num=0;
        line_num = 0;
        gets(line);
        if(line[0]=='t'){
        // if(strstr(line,"top")>0){
            // printf("TOP \n");
            top(heap, num);
            // if(num>0){
                // print(heap, num);
            // }
        }else if(line[1]=='o'){
        // }else if(strstr(line,"pop")>0){
            // printf("POP \n");
            pop(heap, num);
            if(num>0){
                num--;
            }
            // else{
                // print(heap, num);
            // }
        }else{
            strtok(line, " ");
            char* ttt = strtok(NULL, "\n");
            line_num = atoi(ttt);
            // printf("PUSH ");
            // printf("%d \n",line_num);
            push_x(heap, num, line_num);
            num++;
            // print(heap, num);
        }
    }
    return 0;
}