harithwayn818的部落格

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

#define MAX_SIZE 100
#define INFINITY 2147483647

void print(int list[], int n);
void insert(int list[], int key, int n);
void minHeapInsert(int list[], int pos, int key, int n);
void maxHeapInsert(int list[], int pos, int key, int n);
int deleteMin(int list[], int n);
int deleteMax(int lsit[], int n);

int main()
{
    char manual[] = "menu: 1.insert 2.deleteMin 3.deleteMax 4.print(just reference) 5.exit op:";
    int op;

    int key;

    int list[MAX_SIZE];
    int n = 1;

    list[1] = INFINITY;

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

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

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

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

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

            case 5:
                exit(0);
        }
    }

    return 0;
}

void insert(int list[], int key, int n)
{
    /*if(n > MAX_SIZE){
        printf("Heap is full! ");
        return;
    }*/

    int leftMost = 2;
    while(leftMost <= n)
        leftMost <<= 1;
    leftMost >>= 1;
    if(n > leftMost + leftMost/2 - 1)
        maxHeapInsert(list, n, key, n);
    else
        minHeapInsert(list, n, key, n);

}

void minHeapInsert(int list[], int pos, int key, int n)
{
    int pair;
    int posLevel;
    int tmp;

    for(tmp = pos, posLevel = 0; tmp; tmp>>=1)
        posLevel++;

    tmp = 1;
    for(int i = 1; i<posLevel-1; i++) // log pos = posLevel-1
        tmp <<= 1;

    pair = pos + tmp;  // pair = pos + 2^(log pos - 1)
    
    if(pair >= n)
        pair /= 2;

    if(key > list[pair]){
        list[n] = list[pair];
        maxHeapInsert(list, pair, key, n);
    }
    else{
        int tmp = pos;
        int parent = pos/2;
        while(parent >= 2){
            if(key >= list[parent])
                break;
            list[tmp] = list[parent];
            tmp = parent;
            parent/=2;
        }
        list[tmp] = key;
    }
}

void maxHeapInsert(int list[], int pos, int key, int n)
{
    int pair;
    int posLevel;
    int tmp;

    for(tmp = pos, posLevel = 0; tmp; tmp>>=1)
        posLevel++;

    tmp = 1;
    for(int i = 1; i<posLevel-1; i++)
        tmp <<= 1;

    pair = pos + tmp;

    if(pair >= n)
        pair /= 2;

    if(key < list[pair]){
        list[n] = list[pair];
        minHeapInsert(list, pair, key, n);
    }
    else{
        int tmp = pos;
        int parent = pos/2;
        while(parent >= 2){
            if(key <= list[parent])
                break;
            list[tmp] = list[parent];
            tmp = parent;
            parent/=2;
        }
        list[tmp] = key;
    }
}

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

    n--;
    int minValue = list[2];
    int child = 4;
    while(child <= n){
        if(child < n && list[child] > list[child+1])
            child ++;

        list[child/2] = list[child];
        child *= 2;
    }

    minHeapInsert(list, child/2, list[n+1], n);

    return minValue;
}

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

    n--;
    int maxValue = list[3];
    int child = 6;
    while(child <= n){
        if(child < n && list[child] < list[child+1])
            child ++;

        list[child/2] = list[child];
        child *= 2;
    }

    maxHeapInsert(list, child/2, list[n+1], n);

    return maxValue;
}

void print(int list[], int n)
{
    if(n<1){
        printf("Heap is empty ");
        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(" ");
    }
}