C++怎么实现优先队列-创新互联

这篇文章主要介绍C++怎么实现优先队列，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

为阳春等地区用户提供了全套网页设计制作服务，及阳春网站建设行业解决方案。主营业务为成都做网站、网站设计、阳春网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

C++ 实现优先队列的简单实例

优先队列类模版实现：

BuildMaxHeap.h头文件：

#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; 
  } 
  //此处逻辑判断出错，开始为else if，发现不能正确排序，改为else之后正确 
  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); 
  } 
} 
//此处添加利用循环方式代替递归Max_Heapify的函数，该函数可以替代Max_Heapify 
//在某些情况下能取得更好 的效果 
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; 
    } 
    //此处逻辑判断出错，开始为else if，发现不能正确排序，改为else之后正确 
    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; 
}

以上是“C++怎么实现优先队列”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联网站建设公司行业资讯频道！

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

本文题目：C++怎么实现优先队列-创新互联
标题网址：https://www.cdcxhl.com/article36/pgssg.html

成都网站建设公司_创新互联，为您提供网站导航、网站策划、网站内链、定制网站、网站制作、网站收录

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联