MinHeap::MinHeap(const int n)
{
        CurrentSize = 0;
        MaxSize = n;
        heapArray = new junction[MaxSize];
}
bool MinHeap::empty()
{
        if (CurrentSize == 0)
                return true;
        else
                return false;
}
void MinHeap::swap(int x, int y)
{
        junction temp = heapArray[x];
        heapArray[x] = heapArray[y];
        heapArray[y] = temp;
}
int MinHeap::parent(int pos) const
{
        return (pos-1)/2;
}
bool MinHeap::Insert(const junction& newNode)
{
        if (CurrentSize == MaxSize)
                return false;
        heapArray[CurrentSize] = newNode;
        SiftUp(CurrentSize);
        CurrentSize ++;
        return true;
}
void MinHeap::SiftUp(int position)
{
        int temppos = position;
        junction temp = heapArray[temppos];
        while((temppos > 0) && (heapArray[parent(temppos)].length > temp.length))
        {
                heapArray[temppos] = heapArray[parent(temppos)];
                temppos = parent(temppos);
        }
        heapArray[temppos] = temp;
}
junction& MinHeap::RemoveMin()
{
        if (CurrentSize == 0)
        {
                cout<<"can't delete";
                exit(1);
        }
        else
        {
                swap(0, --CurrentSize);
                if(CurrentSize > 1)
                        SiftDown(0);
                return heapArray[CurrentSize];
        }
}
void MinHeap::SiftDown(int left)
{
        int i = left;
        int j = 2 * left + 1;
        junction temp = heapArray[i];

        while (j < CurrentSize)
        {
                if ((j < CurrentSize-1) && (heapArray[j].length > heapArray[j+1].length))
                        j++;
                if (temp.length > heapArray[j].length)
                {
                        heapArray[i] = heapArray[j];
                        i = j;
                        j = 2 * i + 1;
                }
                else
                        break;
        }
        heapArray[i] = temp;
}
