优先级队列.txt

常见算法

#include<iostream>
using namespace std;
int heapsize,length;                            //定义两个全局变量
int parent(int i)
{
	if(i%2) return (i-1)/2;
	else return (i-2)/2;
}
void heapify(int a[],int i)                     //保持堆性质函数
{
int l,r,max,t;
l=2*i+1;                                        //计算以序号i为根的左子树序号　　　　　　　　　　　　　　　　　　　　　
r=2*i+2;                                        //计算以序号i为根的右子树序号
if(l<=heapsize && a[l]>a[i])
   max=l;
else
   max=i;
if(r<=heapsize && a[r]>a[max])
   max=r;
if(max!=i)
{t=a[i];a[i]=a[max];a[max]=t;heapify(a,max);}
}

void build_heap(int a[])                        //建堆函数
{
int i;
for(i=length/2-1;i>=0;i--)
   heapify(a,i);

}int heap_extract_max(int a[])                 //去掉并返回堆中具有最大关键字的元素
{
    int max;
	heapsize=sizeof(a)/sizeof(a[0])-1;
    if(heapsize<0){cout<<"Heap underflow!"<<endl; return 0;}
	max=a[0];
	a[0]=a[heapsize];
	heapsize--;
	heapify(a,0);
	return max; 
}
void heap_insert(int a[],int key)              //插入一个关键字为key的节点
{
	int i;
	heapsize++;
	i=heapsize;
	while(i>0 && a[parent(i)]<key)
	{
		a[i]=a[parent(i)];
		i=parent(i);
	}
	a[i]=key;
}
void main()
{
int a[11]={4,1,3,2,16,9,10,14,8,7},i;
length=sizeof(a)/sizeof(a[0]);
heapsize=sizeof(a)/sizeof(a[0])-2;
for(i=0;i<10;i++)
   cout<<a[i]<<"  ";
cout<<endl;
build_heap(a);
for(i=0;i<10;i++)
   cout<<a[i]<<"  ";
cout<<endl;
heap_insert(a,15);
for(i=0;i<length;i++)
   cout<<a[i]<<"  ";
cout<<endl;
}