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

#define MinPQSize (10)
#define MinData (-32767)

struct HeapStruct {
    int Capacity;
    int Size;
    gutuie *Elements;
};

PriorityQueue Initialize(int MaxElements) {
    PriorityQueue H;

    /* 1*/ if (MaxElements < MinPQSize)
        /* 2*/ printf("Priority queue size is too small");

    /* 3*/ H = malloc(sizeof ( struct HeapStruct));
    /* 4*/ if (H == NULL)
        /* 5*/ printf("Out of space!!!");

    /* Allocate the array plus one extra for sentinel */
    /* 6*/ H->Elements = malloc((MaxElements + 1)
            * sizeof (gutuie));
    /* 7*/ if (H->Elements == NULL)
        /* 8*/ printf("Out of space!!!");

    /* 9*/ H->Capacity = MaxElements;
    /*10*/ H->Size = 0;
    	gutuie Min;
    	Min.m = MinData; 
    /*11*/ H->Elements[ 0 ] = Min;

    /*12*/ return H;
}

/* END */

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

/* H->Element[ 0 ] is a sentinel */

void Insert(gutuie X, PriorityQueue H) {
    int i;

    if (IsFull(H)) {
        printf("Priority queue is full");
        return;
    }

    for (i = ++H->Size; (H->Elements[ i / 2 ]).m < X.m; i /= 2)
        H->Elements[ i ] = H->Elements[ i / 2 ];
    H->Elements[ i ] = X;
}

/* END */


gutuie DeleteMax(PriorityQueue H) {
    int i, Child;
    gutuie MinElement, LastElement;

    /* 1*/ if (IsEmpty(H)) {
        /* 2*/ printf("Priority queue is empty");
        /* 3*/ return H->Elements[ 0 ];
    }
    /* 4*/ MinElement = H->Elements[ 1 ];
    /* 5*/ LastElement = H->Elements[ H->Size-- ];

    /* 6*/ for (i = 1; i * 2 <= H->Size; i = Child) {
        /* Find smaller child */
        /* 7*/ Child = i * 2;
        /* 8*/ if (Child != H->Size && (H->Elements[ Child + 1 ]).m
                /* 9*/ > (H->Elements[ Child ]).m)
            /*10*/ Child++;

        /* Percolate one level */
        /*11*/ if (LastElement.m < (H->Elements[ Child ]).m)
            /*12*/ H->Elements[ i ] = H->Elements[ Child ];
        else
            /*13*/ break;
    }
    /*14*/ H->Elements[ i ] = LastElement;
    /*15*/ return MinElement;
}

gutuie FindMax(PriorityQueue H) {
    if (!IsEmpty(H))
        return H->Elements[ 1 ];
    printf("Priority Queue is Empty");
    return H->Elements[ 0 ];
}

int IsEmpty(PriorityQueue H) {
    return H->Size == 0;
}

int IsFull(PriorityQueue H) {
    return H->Size == H->Capacity;
}

void Destroy(PriorityQueue H) {
    free(H->Elements);
    free(H);
}