赞
踩
注:堆是一种完全二叉树;
大根堆即根节点的值>=其左右子树根节点的值;
小根堆即根节点的值<=其左右子树根节点的值。
完全二叉树特点:
创建一棵完全二叉树即按层创建一棵二叉树,不可用递归创建。
:`
typedef struct node{
int data;
struct node *left,*right;
}HeapNode;
//创建完全二叉树
HeapNode *CreatTree(int *Data,int n,HeapNode **Q)
{
//队列初始化(0号不用)
int front,rear,pa,i;
HeapNode *root;
front=0;
rear=0;
pa=1;
//创建并初始化根节点
root=(HeapNode *)malloc(sizeof(HeapNode));
root->data=Data[0];
root->left=NULL;
root->right=NULL;
Q[++rear]=root;
//遍历数据集合建树
for(i=1;i
代码如下
typedef struct node{
int data;
struct node *left,*right;
}HeapNode;
//堆排序
void HeapSort(HeapNode *root,HeapNode **Q,int n)
{
int rear=n;//尾指针等于数据域Q的元素个数
int pa;
int tag;
int temp;
int i;
//利用循环对除根节点之外的结点排序
while(rear>1)
{
//利用死循环将二叉树调成一个大根堆
while(1)
{
//利用循环把二叉树调节一次!!!!!
for(tag=0,pa=rear/2;pa>0;pa--)
{
if(Q[pa]->data<Q[pa]->left->data)
{
temp=Q[pa]->data;
Q[pa]->data=Q[pa]->left->data;
Q[pa]->left->data=temp;
tag=1;
}
if(Q[pa]->right&&Q[pa]->data<Q[pa]->right->data)
{
temp=Q[pa]->data;
Q[pa]->data=Q[pa]->right->data;
Q[pa]->right->data=temp;
tag=1;
}
}
if(tag==0)
break;
}
//交换大根堆中最后一个结点与根结点的数值
temp=Q[rear]->data;
Q[rear]->data=Q[1]->data;
Q[1]->data=temp;
//在树上将最后一个结点断链删去
//可以利用rear的奇偶性判断最后一个结点是其双亲的左子女还是右子女
//也可以直接用双亲的左是否为空来判断
if(rear%2)
Q[rear/2]->right=NULL;
else
Q[rear/2]->left=NULL;
//在数组中将利用尾指针将当前最后一个元素排除在下次排序之外
rear--;
}
/*输出利用大根堆排序的结果---降序排列。需要逆序输出数组Q对应的结点的数据*/
printf("The result of HeapSort is:\n");
for(i=n;i>0;i--)
{
printf("%5d",Q[i]->data);
}
}
int main(void)
{
HeapNode *root;
HeapNode **Q;
int *Data;
int n,i;
printf("Please input the number of the data");
scanf("%d",&n);
Data=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
scanf("%d",&Data[i]);
}
//队列创建
Q=(HeapNode **)malloc((n+1)*sizeof(HeapNode *));
//创建完全二叉树
root=CreatTree(Data,n,Q);
OutPrintTree(root,0);
//堆排序
HeapSort(root,Q,n);
return 0;
}
代码优化方法:
不用完全二叉树,直接用舍弃0号单元数组存值,利用数组下标即可判断值在完全二叉树中的位置。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。