[数据结构与算法]堆排序

堆排序说是堆 其实还是用树来进行考究分析

对于父结点 子结点的规律可以自己试一下

父结点中的值大于两个子结点中的值 才可构成所谓完整的堆

假设一个结点坐标为i

那么这个结点的父结点坐标为 (i-1)/2? 两个子结点的坐标分别为 2*i+1 2*i+1

本次实现三个主要的函数 后面分析

首先写出主函数

#include<stdio.h>
int main()
{
	int tree[] = { 4,10,3,5,1,2 };
	int n = sizeof(tree) / sizeof(tree[0]);
	heaplify(tree, n, 0);//tree代表对这棵树 n表示这棵树有n个元素 0表示从下标0开始heaplify
	build_heap(tree, n);
	heap_sort(tree, n);
	return 0;
}

1.实现heaplify函数 作用：把父结点中的值都调节为大于对应子结点的值?

代码如下

void heaplify(int tree[], int n, int i)
{
	if (i >= n) 
	{
		return ;//超出边界 什么都不返回
	}
	int c1 = 2 * i + 1;
	int c2 = 2 * i + 2;//两个子结点的坐标
	int max = tree[i];//先顺应规则要求 令最大值为顶点
	//判断是否顶点为max
	if (c1<n && tree[c1]>max)
	{
		max = tree[c1];
	}
	if (c2<n && tree[c2]>max)
	{
		max = tree[c2];
	}
	//倘若最大值max变化了 则须换位
	if (max != tree[i])
	{
		int temp = max;
		max = tree[i];
		tree[i] = temp;
		//递归 因为max调换到下位时不一定大于它下面两个子结点的值 因此须递归max
		heaplify(tree, n , max);
	}
}

2.实现build_heap函数 作用：从最后一个顶点依次往上找相对顶点排序 保证父结点大于两个子结点

代码如下

void build_heap(int tree[], int n)
{
	int last = n - 1;//最后一个结点的下标为元素数减一
	//最后一个相对的父结点
	int fuLast = (n - 1) / 2;
	int i = 0;
	for (i = fuLast; i >= 0; i--)
	{
		heaplify(tree, n,i);
	}
}

3.heap_sort函数 作用：通过heaplify函数排序之后把每一个结点拽下来 排一下横序

用俗话就是砍下来 按顺序排好

void swap(int tree[], int i, int n)
{
	int temp = tree[i];
	tree[i] = tree[n];
	tree[n] = temp;
}
void heap_sort(int tree[], int n)
{
	//首先创建一个完整的堆
	build_heap(tree, n);
	int i = 0;
	for (i = n - 1; i >= 0; i--)
	{
		swap(tree, i, 0);//完整的堆最上面的根结点一定最大 把它换下去砍了 每次换最大的 砍去最大的 自己想一想
		heaplify(tree, i, 0);//每次砍一刀 掉一个结点 随着i变化
	}
}