Priority Queue implementation using MaxHeap

The Priority Queue with a MaxRemove() interface can be implemented using a MaxHeap which is a complete binary tree that maintains the maximum (here it would be the maximum of the priority values) of the elements that it contains at its root.

The Code is super simple and is as follows:

[code language="cpp"]

PriorityQueue(int CapacityParam)
{
Data = (int*)malloc(CapacityParam*sizeof(int));
ToH = -1;
Capacity = CapacityParam;
}

void Display()
{
cout << "\nList:\n";
for (int iter = 0; iter <= ToH; iter++)
cout << " " << Data[iter];
}

void HeapifyUp(int Position)
{
if (Position < 1) return;
if (Data[Position]>Data[(Position - 1) / 2])
{
Swap(&(Data[Position]), &(Data[(Position - 1) / 2]));
HeapifyUp((Position - 1) / 2);
}
}

bool Insert(int ParamValue)
{
if (ToH >= Capacity - 1) return false; //QueueOverflow
Data[++ToH] = ParamValue;
HeapifyUp(ToH);
return true;
}

void HeapifyDown(int Position)
{
if (2 * Position + 1 > ToH) return;
if (2 * Position + 2 <= ToH)
{
//LR exists
if (Data[2 * Position + 1] > Data[2 * Position + 2])
{
//L
if (Data[2 * Position + 1] > Data[Position]) Swap(&(Data[2 * Position + 1]) ,& (Data[Position]));
HeapifyDown(2 * Position + 1);
}
else
{
//R
if (Data[2 * Position + 2] > Data[Position]) Swap(&(Data[2*Position+2]), &(Data[Position]));
HeapifyDown(2 * Position + 2);
}
}
else
{
//Only L exists
//L
if (Data[2 * Position + 1] > Data[Position]) Swap(&(Data[2 * Position + 1]), &(Data[Position]));
HeapifyDown(2 * Position + 1);
}
}

void SortDump()
{
int SortToH = ToH;
while (ToH >= 0)
{
Swap(&(Data[0]), &(Data[ToH]));
--ToH;
HeapifyDown(0);
}
ToH = SortToH;
Display();
}
};

void FillArrayWithRand(int *Array, int Size)
{
if (!Array || Size<=0) return;
for (int i = 0; i < Size; i++)
Array[i] = (rand() % 10);
}
int main()
{
//Dont allow 0 in the tree for CommonAncestor problem

const int DataSetSize = 9999;
int *RandArray = (int*)malloc(DataSetSize * sizeof(int));
FillArrayWithRand(RandArray, DataSetSize);
cout << "\nRandom Array:\n";
for (int i = 0; i < DataSetSize; i++)
cout<<" "<<RandArray[i];

PriorityQueue test(DataSetSize);
for (int i = 0; i < DataSetSize; i++)
test.Insert( RandArray[i]);
test.Display();
test.SortDump();

cout << "\n\nEnd of code";
system("pause");

return 0;
}

&nbsp;

[/code]