堆的应用

一：堆排序算法

#include <iostream>
#include <math.h>
using namespace std;

#define LEFT(i) (2*(i)+1)
#define RIGHT(i) (2*(i)+2)

//           16(0)
//          /     \  
//       10(1)    8(2)	
//        /  \        
//    9(3)   7(4)

//n为5，叶子节点序号为2,3,4  ->floor(5/2).....n

void exchange(int& a,int& b)
{
	int tmp=a;
	a=b;
	b=tmp;
}

void printArray(int a[],int n)
{
	for(int i=0;i<n;++i)
		cout<<a[i]<<" ";
	cout<<endl;
}

void maxHeapify(int a[],int i,int n)  // 使以i为根的子树成为最大堆
{
	int l=LEFT(i);
	int r=RIGHT(i);
	int heapindex=n-1;
	int largest;
	if((l<=heapindex)&&(a[l]>a[i]))
		largest=l;
	else
		largest=i;

	if((r<=heapindex)&&(a[r]>a[largest]))
		largest=r;

	if(largest!=i)
	{
		exchange(a[i],a[largest]);	
		maxHeapify(a,largest,n);  //由于大小对换了，所以对调的那个有可能就不满足最大堆的性质了
	}
}

/* 构建最大堆
数组A[floor(n/2)..n]中的元素都是树中的叶子，所以要对树中的每一个其它节点调用maxHeapify(),让每一个
节点都满足最大堆的性质 ,注意顺序：从最后一个非叶子节点到根*/
void buildMaxHeap(int a[],int n)
{
	for(int i=floor(n/2)-1;i>-1;--i)
		maxHeapify(a,i,n);
}

/*堆排序 
先构建好最大堆，有最大堆性质可知根元素是最大的，把根与最后一个元素交换，让新根调用maxHeapify()
*/
void heapSort(int a[],int n)
{
	buildMaxHeap(a,n);
	for(int i=n-1;i>0;--i)
	{
		exchange(a[0],a[i]);
		maxHeapify(a,0,i);
	}
}

int main()
{
int a[10]={16,4,10,14,7,9,3,2,8,1};
heapSort(a,10);
printArray(a,10);


cout<<endl;
}

运行结果：
1 2 3 4 7 8 9 10 14 16

总结：

1.可以在线性时间内，将一个无序数组建成一个最大堆

2.堆排序时间复杂度为nlgn,但在实践中，快速排序往往优于堆排序

二：实现优先级队列

这里使用基于最大堆实现的最大优先级队列(模拟简单作业调度)

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <math.h>
using namespace std;
#define PARENT(i)  ((int)floor(((i)-1)/2))  //堆中节点为i的父节点号(从0开始)
#define LEFT(i) (2*(i)+1)    
#define RIGHT(i) (2*(i)+2)


typedef struct job
{
	unsigned jobid; //作业号
	unsigned  pid; //进程pid
	char name[10];    //作业name
	int priority; //优先级
}*Pjob;

int current=0;  //当前索引,从0开始
void exchange(char*& s,char*& d)
{
	char *tmp=s;
	s=d;
	d=tmp;
}

void jobAdd(char **JobTable,Pjob p)
{
	int i=current;
	JobTable[current]=(char*)p;
	while(i>0)
	{
		if(((Pjob)JobTable[i])->priority > ((Pjob)JobTable[PARENT(i)])->priority)  //比较优先级
		{
			exchange(JobTable[i],JobTable[PARENT(i)]);
			i=PARENT(i); //继续和上一级比较 
		}
		else
			break;
	}
	++current;
}

void maxHeapify(char **JobTable,int i)   //使以i为根的子树成为最大堆
{
	int l=LEFT(i);
	int r=RIGHT(i);
	int largest=i;
	if(l<=current-1&&((Pjob)JobTable[l])->priority > ((Pjob)JobTable[i])->priority)
		largest=l;
	if(r<=current-1&&((Pjob)JobTable[r])->priority > ((Pjob)JobTable[largest])->priority)
		largest=r;

	if(largest!=i)
	{
		exchange(JobTable[i],JobTable[largest]);
		maxHeapify(JobTable,largest);
	}
}

void doJob(char **JobTable)
{
	Pjob now=(Pjob)JobTable[0];
	cout<<"作业号:"<<now->jobid
		<<"    "<<now->name
		<<"    "<<now->pid
		<<"    "<<now->priority<<"  done!!!"<<endl;

	free(JobTable[0]);
	--current;
	if(current!=0)
	{
		JobTable[0]=JobTable[current];
		maxHeapify(JobTable,0);  //交换完后需要重新保持最大堆性质
	}
}

int main()
{
	char *JobTable[10]={0};

	Pjob bash=(Pjob)malloc(sizeof(struct job));
	bash->jobid=1;
	bash->pid=4321;
	strcpy(bash->name,"bash");
	bash->priority=12;

	Pjob vi=(Pjob)malloc(sizeof(struct job));
	vi->jobid=2;
	vi->pid=4325;
	strcpy(vi->name,"vivi");
	vi->priority=16;


	Pjob perl=(Pjob)malloc(sizeof(struct job));
	perl->jobid=4;
	perl->pid=4329;
	strcpy(perl->name,"perl");
	perl->priority=20;

	Pjob qq=(Pjob)malloc(sizeof(struct job));
	qq->jobid=3;
	qq->pid=4349;
	strcpy(qq->name,"qqqq");
	qq->priority=30;

	Pjob cs=(Pjob)malloc(sizeof(struct job));
	cs->jobid=5;
	cs->pid=4345;
	strcpy(cs->name,"cscs");
	cs->priority=18;

	jobAdd(JobTable,bash);
	jobAdd(JobTable,vi);
	jobAdd(JobTable,perl);
	jobAdd(JobTable,qq);
	jobAdd(JobTable,cs);

	doJob(JobTable);
	doJob(JobTable);
	doJob(JobTable);
	doJob(JobTable);
	doJob(JobTable);
	cout<<endl;
}

运行结果：

作业号:3    qqqq    4349    30  done!!!
作业号:4    perl    4329    20  done!!!
作业号:5    cscs    4345    18  done!!!
作业号:2    vivi    4325    16  done!!!
作业号:1    bash    4321    12  done!!!

基于堆的优先级时间复杂度是lgn。