# C++ implements a simple example of a priority queue

• 2020-05-27 06:50:42
• OfStack

C++ implements a simple example of a priority queue

Priority queue class template implementation:

``````
#include<iostream>
using namespace std;
#define Left(i) i*2+1
#define Right(i) i*2+2
#define Parent(i) (i-1)/2
void Max_Heapify(int a[],int length,int i)
{
int left,right;
left=Left(i);
right=Right(i);
int num=i;
if(left<length&&a[left]>a[i])
{
num=left;
}
// There is a logic error here, starting with else if , found that the order could not be sorted correctly else Right after
if(right<length&&a[right]>a[num])
{
num=right;
}
if(num!=i)
{
int temp;
temp=a[i];
a[i]=a[num];
a[num]=temp;
Max_Heapify(a,length,num);
}
}
// Add a loop instead of recursion here Max_Heapify , which can be substituted Max_Heapify
// In some cases it can be better   The effect of
void Max_Heapify1(int a[],int length,int i)
{
int left,right,num=i,largest=i;
left=Left(i);
right=Right(i);
while(1)
{
if(a[left]>a[num]&&left<length)
{
largest=left;
}
// There is a logic error here, starting with else if , found that the order could not be sorted correctly else Right after
if(a[right]>a[largest]&&right<length)
{
largest=right;
}
if(num!=largest)
{
int temp;
temp=a[num];
a[num]=a[largest];
a[largest]=temp;
num=largest;
left=Left(num);
right=Right(num);
}
else
{
break;
}
}

}
void Build_Max_Heap(int a[],int length )
{
int i;
for(i=(length-1)/2;i>=0;i--)
{
Max_Heapify1(a,length,i);
}
}

void Heap_Sort(int a[],int length)
{
Build_Max_Heap(a,length);
int i;
int temp;
for(i=length-1;i>=1;i--)
{
temp=a[i];
a[i]=a[0];
a[0]=temp;
length-=1;
Max_Heapify1(a,length,0);
}
}
``````

PriorQUeue.h

``````
#include<iostream>
#include "BuileMaxHeap.h"
using namespace std;
#define MAX 100
template <typename type>class PriorQueue
{
private:
int length;
type a[MAX];
public:
PriorQueue ()
{
int i;
length=0;

for(i=0;i<MAX;i++)
{
a[i]=0;
}
}
~PriorQueue()
{

}
void BuildMaxHeapQueue();
void Init(type b[],int len);
type Maxnum();
bool DeleteMax();
void IncreaseKey(int i,type key);
void Insert(type key);
void Print();
void Sort();
};
template<typename type>void PriorQueue<type>::Init(type b[],int len)
{
int i;
this->length=len;
if(len<=0)
{
cout<<"Init failed !"<<endl;
}
for(i=0;i<len;i++)
{
a[i]=b[i];
}
BuildMaxHeapQueue();
}
template<typename type>void PriorQueue<type>::BuildMaxHeapQueue()
{
Build_Max_Heap(a,length);
}
template<typename type>type PriorQueue<type>::Maxnum()
{
if(length<=0)
{
cout<<"the queue is empty!"<<endl;
return -1;
}
return a[0];
}
template<typename type>bool PriorQueue<type>::DeleteMax()
{
if(length<=0)
{
cout<<"the queue is empty!"<<endl;
return 0;
}
a[0]=a[length-1];
length-=1;
Max_Heapify1(a,length,0);
return 1;
}
template<typename type>void PriorQueue<type>::IncreaseKey(int i,type key)
{
int num=i;
if(key<a[num])
{
cout<<"key is error!"<<endl;
return ;
}
a[num]=key;
while(num>0&&a[Parent(num)]<a[num])
{
type temp;
temp=a[num];
a[num]=a[Parent(num)];
a[Parent(num)]=temp;
num=Parent(num);
}
}

template<typename type>void PriorQueue<type>::Insert(type key)
{
if(length>=MAX)
{
cout<<"the queue is full can't add more!"<<endl;
return ;
}
length+=1;
a[length-1]=key;
IncreaseKey(length-1,key);
}
template<typename type>void PriorQueue<type>::Print()
{
int i;
for(i=0;i<length;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
template<typename type>void PriorQueue<type>::Sort()
{
Heap_Sort(a,length);
}

``````

main.cpp

``````
#include"PriorQueue.h"
#include<iostream>
using namespace std;

int main()
{
PriorQueue<int> node;
int b[10]={4,1,3,2,16,9,10,14,8,7};
node.Init(b,10);
int i;
node.Print();
cout<<endl;
cout<<node.Maxnum()<<endl;
node.DeleteMax();
node.Print();
node.Insert(232);
node.Sort();
node.Print();
return 0;
}

``````

The above is the data structure priority queue example, if you have questions please leave a message or to the site community exchange discussion, thank you for reading, hope to help you, thank you for the support of the site!

Related articles: