//Heap(priority)
//-------- PQueue.cpp ------------
//---------------------------------------------------------------------------
#pragma package(smart_init)

PQueue::PQueue(int capacity)
{
    Array = new QueueData[capacity];
    Capacity = capacity;
    Size = 0;
}

PQueue::~PQueue()
{
    delete [] Array;
}

void PQueue::Insert(int priority, const char DataString[], int FilePosition)
{
    if(Capacity == Size)
        return;
    else
    {
        Size++;
        Array[Size].Priority = priority;
        strcpy(Array[Size].DataString, DataString);
        Array[Size].FilePosition = FilePosition;
        int empty;
        for(empty = Size; empty >1 &&  priority < Array[empty/2].Priority; empty = empty/2)
            Array[empty] = Array[empty/2];
        Array[empty].Priority = priority;
    }
}

QueueData PQueue::RemoveMin()
{
    QueueData ReturnData;
    ReturnData.Priority = -1;
    if(Size == 0)
        return ReturnData;
    else
    {
        ReturnData = Array[1];
        //strcpy(ReturnData.DataString, Array[1].DataString);
        Array[1] = Array[Size];
        Size--;
        int child, openSpot;
        for(openSpot = 1; openSpot*2 <= Size; openSpot = child)
        {
            child = openSpot*2;
            if(child!=Size && Array[child+1].Priority > Array[child].Priority)
                child++;
            if(Array[child].Priority > Array[Size+1].Priority)
                Array[openSpot] = Array[child];
            else
                break;
        }
        Array[openSpot] = Array[Size+1];  //size + 1 holds the int that went to the root
        return ReturnData;
    }
}



 




-------- PQueue.h -------------
//---------------------------------------------------------------------------
#ifndef PQueueH
#define PQueueH
//---------------------------------------------------------------------------

struct QueueData
{
    int FilePosition;
    int Priority;
    char DataString[20];
};

class PQueue
{
    public:
        PQueue(int capacity=1000);
        ~PQueue();
        void Insert(int priority, const char[], int);
        QueueData RemoveMin();
        int Size;

    private:

        int Capacity;
        QueueData* Array;
};

#endif