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--)
{