heapsort.cpp

此文件夹中共包括十二个小程序 AVL创建平衡二叉树,通过加入一个个的结点创建,并实现了平衡二叉树中的结点删除 Boyer_Moore算法的串模式匹配 Horspool算法的串模式匹配 Grap

//用堆构造优先级队列，键值越小的优先级越高

#include <stdio.h>
#include <stdlib.h>
#define MAXE 20

void Shift(int R[],int low,int high) //调整堆,建立小根堆
{
	int i=low,j=2*i;  //R[j]是R[i]的左孩子
	int temp=R[i];
	while(j<=high)
	{
		if(j<high&&R[j+1]<R[j])  //若右孩子较小，把j指向右孩子
			j++;
		if(R[j]<temp)  
		{
			R[i]=R[j];  //将R[j]调整到双亲结点位置上
			i=j;      //修改i和j的值，以便继续向下筛选
			j=2*i;
		}
		else break; //筛选结束
	}
	R[i]=temp;     //被筛选结点的值放入最终位置
}

void DispHeap(int R[],int i,int n)  //以括号表示法输出建立的堆
{
	if(i<=n)
		printf("%d",R[i]);	 //输出根结点
	if(2*i<=n||2*i+1<n)
	{
		printf("(");		
		if(2*i<=n)
			DispHeap(R,2*i,n);  //递归调用输出左子树
		printf(",");
		if(2*i+1<=n)
			DispHeap(R,2*i+1,n);  //递归调用输出右子树
		printf(")");
	}
}

//对R[1]到R[n]元素实现堆排序
void HeapSort(int R[],int n)
{
	int i;
	int temp;
	for(i=n/2;i>=1;i--)
		Shift(R,i,n);  //循环建立初始堆

	printf("初始堆: ");  //输出初始堆
	DispHeap(R,1,n);
	printf("\n\n");
	
	for(i=n;i>=2;i--)  //进行n-1次循环，完成堆排序
	{
		printf("交换%d与%d,输出%d\n",R[i],R[1],R[1]);
		temp=R[1];  //将第一个元素同当前区间内R[i]对换
		R[1]=R[i];
		R[i]=temp;
		Shift(R,1,i-1); //筛选R[1]结点，得到i-1个结点的堆
		printf("筛选调整得到堆: ");
		DispHeap(R,1,i-1);
		printf("\n\n");
	}
}


void main()
{
	int i,k,n=10;
	int a[10]={6,8,7,9,0,1,3,2,4,5};
	int R[MAXE];
	for(i=1;i<=n;i++)
		R[i]=a[i-1];

	printf("初始关键字 ");
	for(k=1;k<=n;k++)
		printf("%2d",R[k]);
	printf("\n");

	for(i=n/2;i>=1;i--)              //循环建立初始堆
		Shift(R,i,n);
	HeapSort(R,n);  //堆排序
	printf("\n");

	printf("最终结果为: ");
	for(k=1;k<=n;k++)
		printf("%2d",R[k]);
	printf("\n");

	system("PAUSE");
	
}