Heaps implement Priority Queues

max_heap.c

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

#define MaxData (32767)

typedef struct _bheap{

    int Capacity;
    int Size;
    int *Elements;
} BIN_HEAP;

typedef BIN_HEAP bheap;

BIN_HEAP * Init(int Capacity){

    bheap * newheap;

    newheap = (bheap *)malloc(sizeof(bheap));
    newheap->Capacity = Capacity;
    newheap->Size = 0;

    newheap->Elements = (int *)malloc(sizeof(int));
    newheap->Elements[0] = MaxData;

    return newheap;
}

void MakeEmpty(BIN_HEAP * H){
    H->Size = 0;
}

int IsFull(BIN_HEAP * H){

    return H->Size >= H->Capacity ? 1 : 0;
}

void Insert(int X, BIN_HEAP * H){

    int i;

    //printf("Inserting %d\n",X);

    if(!IsFull(H)) {
    for( i = ++H->Size; H->Elements[i/2] < X; i = i/2)
        H->Elements[i] = H->Elements[i/2];
    //i is the hole
    H->Elements[i] = X;
    }
}

int IsEmpty(BIN_HEAP * H){

    return H->Size == 0;
}

int DeleteMax(BIN_HEAP * H){

    int i, Child;
    int minElement, lastElement;

    if(!IsEmpty(H)){


    minElement = H->Elements[1]; //This is the minimum element, Hole is created here.
    lastElement = H->Elements[H->Size--]; //We decreased the size, so lastElement is hanging

    for(i = 1; i * 2 <= H->Size; i = Child){

        Child = i * 2;
        if(Child != H->Size && H->Elements[Child+1] > H->Elements[Child])
        Child ++;

        if(lastElement < H->Elements[Child])
            H->Elements[i] = H->Elements[Child];
        else
            break;

    }

    H->Elements[i] = lastElement;
    return minElement;
    }
    else
        return H->Elements[0];

}

void printHeap(BIN_HEAP * H){

    int i;

    printf("Heap : ");
    for(i=1; i<=H->Size; i++)
        printf("%d ", H->Elements[i]);

    printf("\n");
}

int main(){

    BIN_HEAP * H;
    int i;
    int arr[] = {68,21,13,16,24,31,65,26,19,32,14};

    H = Init(13);

    for(i = 0; i < 11; i++){
        Insert(arr[i], H);
        //printHeap(H);
        }
    printHeap(H);
    for(i = 0; i < 11; i++)
        printf("%d \n",DeleteMax(H));

}

min_heap.c

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

#define MinData (-32767)

typedef struct _bheap{

    int Capacity;
    int Size;
    int *Elements;
} BIN_HEAP;

typedef BIN_HEAP bheap;

BIN_HEAP * Init(int Capacity){

    bheap * newheap;

    newheap = (bheap *)malloc(sizeof(bheap));
    newheap->Capacity = Capacity;
    newheap->Size = 0;

    newheap->Elements = (int *)malloc(sizeof(int));
    newheap->Elements[0] = MinData;

    return newheap;
}

void MakeEmpty(BIN_HEAP * H){
    H->Size = 0;
}

int IsFull(BIN_HEAP * H){

    return H->Size >= H->Capacity ? 1 : 0;
}

void Insert(int X, BIN_HEAP * H){

    int i;

    if(!IsFull(H)) {
    for( i = ++H->Size; H->Elements[i/2] > X; i = i/2)
        H->Elements[i] = H->Elements[i/2];
    //i is the hole
    H->Elements[i] = X;
    }
}

int IsEmpty(BIN_HEAP * H){

    return H->Size == 0;
}

int DeleteMin(BIN_HEAP * H){

    int i, Child;
    int minElement, lastElement;

    if(!IsEmpty(H)){


    minElement = H->Elements[1]; //This is the minimum element, Hole is created here.
    lastElement = H->Elements[H->Size--]; //We decreased the size, so lastElement is hanging

    for(i = 1; i * 2 <= H->Size; i = Child){

        Child = i * 2;
        if(Child != H->Size && H->Elements[Child+1] < H->Elements[Child])
        Child ++;

        if(lastElement > H->Elements[Child])
            H->Elements[i] = H->Elements[Child];
        else
            break;

    }

    H->Elements[i] = lastElement;
    return minElement;
    }
    else
        return H->Elements[0];

}

void printHeap(BIN_HEAP * H){

    int i;

    printf("Heap : ");
    for(i=1; i<=H->Size; i++)
        printf("%d ", H->Elements[i]);

    printf("\n");
}

int main(){

    BIN_HEAP * H;
    int i;
    int arr[] = {68,21,13,16,24,31,65,26,19,32,14};

    H = Init(13);

    for(i = 0; i < 11; i++)
        Insert(arr[i], H);

        printHeap(H);

    for(i = 0; i < 11; i++)
        printf("%d \n",DeleteMin(H));

    return 0;
}