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:


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;

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s