大神的世界

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

#define MAX_SIZE 100

void print(int list[], int n);
void insert(int list[], int key, int n);
void verifyMax(int list[], int key, int pos);
void verifyMin(int list[], int key, int pos);
int deleteMin(int list[], int n);
int deleteMax(int list[], int n);

int main()
{
    char manual[] = "menu:\n1.insert\n2.deleteMin\n3.deleteMax\n4.print(just reference)\n5.exit\n\nop:";
    int op;

    int key;

    int list[MAX_SIZE];
    int n = 0;

    while(1){
        printf("%s", manual);
        scanf("%d", &op);

        switch(op){
            case 1:
                printf("\ninsert value:");
                scanf("%d", &key);
                insert(list, key, n++);
                break;

            case 2:
                printf("Min value = %d\n", deleteMin(list, n--));
                break;

            case 3:
                printf("Max value = %d\n", deleteMax(list, n--));
                break; 

            case 4:
                print(list, n);
                break;

            case 5:
                exit(0);
        }
    }
    return 0;
}

void insert(int list[], int key, int n)
{
    n++;
    if(n == 1){
        list[1] = key;
        return;
    }

    int parent = n/2;

    int tmp = parent, level = 0;
    while(tmp){
        tmp>>=1;
        level++;
    }

    if(level%2){ // parent in min level
        if(key < list[parent]){
            list[n] = list[parent];
            verifyMin(list, key, parent);
        }
        else
            verifyMax(list, key, n);
    }
    else{ // parent in max level
        if(key > list[parent]){
            list[n] = list[parent];
            verifyMax(list, key, parent);
        }
        else
            verifyMin(list, key, n);
    }

}

void verifyMax(int list[], int key, int pos)
{
    int tmp = pos;
    int grandparent = pos/4;

    while(grandparent){
        if(key <= list[grandparent])
            break;
        list[tmp] = list[grandparent];
        tmp = grandparent;
        grandparent = grandparent/4;
    }

    list[tmp] = key;
}

void verifyMin(int list[], int key, int pos)
{
    int tmp = pos;
    int grandparent = pos/4;

    while(grandparent){
        if(key >= list[grandparent])
            break;

        list[tmp] = list[grandparent];
        tmp = grandparent;
        grandparent = grandparent/4;
    }

    list[tmp] = key;
}

int deleteMax(int list[], int n)
{
    if(n < 1){
        printf("Heap is empty");
        return -1;
    }

    if(n == 1){
        n = 0;
        return list[1];
    }

    if(n == 2){
        n = 1;
        return list[2];
    }

    if(n == 3){
        n = 2;
        if(list[2] >= list[3]){
            int maxValue = list[2];
            list[2] = list[3];
            return maxValue;
        }
        else
            return list[3];
    }

    int maxValue, pos, tmp;
    
    if(list[2] >= list[3]){
        maxValue = list[2];
        pos = 2;
        tmp = list[n--];
    }
    else{
        maxValue = list[3];
        pos = 3;
        tmp = list[n--];
    }

    while(1){
        if(2*pos > n){ // no child
            list[pos] = tmp;
            break;
        }
        else{
            int maxPos;
            if(4*pos > n){ // no grandchildren
                
                maxPos = list[2*pos] > list[2*pos+1] ? 2*pos : 2*pos+1;
          
                if(list[maxPos] > tmp){
                    list[pos] = list[maxPos];
                    list[maxPos] = tmp;
                }
                else
                    list[pos] = tmp;

                break;
            }
            else{
            
                maxPos = 4*pos;
                for(int i = maxPos+1; i<=maxPos+3 && i >= n; i++)
                    if(list[i] > list[maxPos])
                        maxPos = i;

                if(list[maxPos] > tmp){
                    list[pos] = list[maxPos];
                    if(tmp < list[maxPos/2]){
                        int tmp2 = tmp;
                        tmp = list[maxPos/2];
                        list[maxPos/2] = tmp2;
                    }

                    pos = maxPos;
                }
                else{
                    list[pos] = tmp;
                    break;
                }
            }
        }
    }
    return maxValue;
}

int deleteMin(int list[], int n)
{
    if(n < 1){
        printf("Heap is empty");
        return -1;
    }

    int minValue = list[1];
    int tmp = list[n--];

    int pos = 1;
    while(1){
        if(2*pos > n){ // no child
            list[pos] = tmp;
            break;
        }
        else{
            int minPos;
            if(4*pos > n){ // no grandchildren
                
                minPos = list[2*pos] < list[2*pos+1] ? 2*pos : 2*pos+1;
          
                if(list[minPos] < tmp){
                    list[pos] = list[minPos];
                    list[minPos] = tmp;
                }
                else
                    list[pos] = tmp;

                break;
            }
            else{
            
                minPos = 4*pos;
                for(int i = minPos+1; i<=minPos+3 && i>=n; i++)
                    if(list[i] < list[minPos])
                        minPos = i;

                if(list[minPos] < tmp){
                    list[pos] = list[minPos];
                    if(tmp > list[minPos/2]){
                        int tmp2 = tmp;
                        tmp = list[minPos/2];
                        list[minPos/2] = tmp2;
                    }

                    pos = minPos;
                }
                else{
                    list[pos] = tmp;
                    break;
                }
            }
        }
    }
    return minValue;
}

void print(int list[], int n)
{
    if(n<1){
        printf("Heap is empty\n\n");
        return;
    }

    for(int i = 1, level = 0; i<=n; i*=2, level++){

        int j = i;
        for(int k = 20-2*level; k>0; k--)
            printf("_");

        for(int j = 0; j<i && i+j <= n; j++){

            for(int k = 10-2*level; k>0; k--)
                printf("_");

            printf("%d", list[i+j]);

        }

        printf("\n");
    }
}