初识堆排序

@(堆排序)

1.什么是堆？

堆是一类特殊数据结构的统称。堆的逻辑结构是一颗完全二叉树。堆排序是利用堆这种数据结构而设计的一种排序方法。

2.堆排序

堆分为最大堆（根最大，也叫大根堆）和最小堆（根最小，也叫小根堆）俩种堆
堆排序结构性：用数组表示的完全二叉树ng)

堆排序思想： 利用堆排序对数组进行排序，从而形成大根堆或小根堆。
例如数组

形成的大根堆和小根堆（0，1，2这些数字是数组的下标）

那么这是怎么形成的呢？
让我们一起来揭晓，首先，堆是一颗完全二叉树，树有双亲和左右孩子，在堆排中，它们的下标父子关系是这样的：leftchild = parent * 2 + 1，rightchild = parent * 2 + 2；parent = （child-1）/2（这里的child可以是leftchild，也可以是rightchild），我们将传进来的数组当成一个堆，接下来要利用到 向下调整算法 而要使用向下调整算法是有要求的，向下调整算法的前提 是左右子树是大根堆或小根堆，而这时传进来是的数组要怎么使它变大根堆或小根堆呢？这就要设计我们的建堆了。

建堆

图1:圆里面的是数组的值，旁边的是下标
例如图1：正调：传过来的数组被我们看成是这样的一颗完全二叉树，那么我们要怎么调呢，才能使它变成小根堆（这里讲小根堆）如果我们正着调，从根开始，将根与它的左右子树中小的比较，若根小于它，则根与小的那个不交换，若根大于它了，则交换，调完根之后，接着往后调，直到叶子节点才停止（叶子节点不用调，叶子节点子树为空）（这也是向下调整算法的思想）
倒着调：既然遇到叶子节点就可以结束了，那么可不可以倒着调呢，答案是可以的，从最后一个非叶子节点开始调，每次调完，往前走，接着又调，又走，直到调完下标为0.
那么，最后一个非叶子节点的下标怎么求呢？如图1，最后一个非叶子节点的值是5，下标是3，这是我们从图看出来的，该怎么求呢，哦，我们可以通过值为1，下标为8的节点来求，值为1和值为5的节点构成父子关系，
所以5的下标x = （8-1）/2 = 3； 而值为1的下标又等于n-1
所以最后一个非叶子节点的下标 = （n-1-1）/2；

排序

1.升序数组建什么堆？

答案是建大根堆，如果是建小根堆，最小的元素堆排序完之后，我们取走最小的元素（根）之后，让后面的继续排，又排出第二小的元素，但是，我们在取出最小元素之后，这个堆的结构就乱了，之前的父子关系被打乱了，应为此时是下标为1作为根，所以，我们又要重新建堆才能继续选，而建堆的时间为o（n），这么一折腾下来，时间效率又被降低了，那如果我们建大根堆呢？排完大根堆后，我们将最大的数（根）与数组的最后一个元素交换，此时，根的左右子树仍是大根堆，（结构未乱），我们又可以接着使用向下调整算法，在找到第二大的元素，不过，此时，应该排除掉我们交换完的最大数。

代码

1.建堆代码`

for (j = (end - 1) / 2; j >= 0; j--)
{
	_HeapSort(a, n, j);//倒着调，每一个都要走一遍
}
void _HeapSort(int* a, int n, int root)//建大根堆
{
	int parent = root;
	int child = parent * 2 + 1;//默认是左孩子
	while (child < n)
	{
		if (a[child + 1] > a[child] && child +1<n)//找出左右孩子中大的
		{
			child += 1;
		}
		if (a[child] > parent)//比较父子，若孩子更大，则交换
		{
			Swap(&a[child], &a[parent]);
			parent = child;//交换完记得更新
			child = parent*2 +1;
		}
		else
		{
			break;
		}
	}
}
void Swap(int* a, int* b)//交换函数
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

堆排序代码示例

#include<stdio.h>
#include<stdlib.h>


//函数声明
//堆排序的子函数--建堆
void _HeapSort(int* a, int n, int root);
//交换函数
void Swap(int* a, int* b);
//堆排序
void HeapSort(int* a, int n, int root);

void _HeapSort(int* a, int n, int root)//建大根堆
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (a[child + 1] > a[child] && child +1<n)
		{
			child += 1;
		}
		if (a[child] > parent)
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent*2 +1;
		}
		else
		{
			break;
		}
	}
}


int main()
{
	int num = 0;
	scanf("%d", &num);
	int* a = (int*)malloc(num * sizeof(int));
	int i = 0;
	for (i = 0; i < num; i++)
	{
		scanf("%d", a + i);
	}
	HeapSort(a, num, 0);
	return 0;
}

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void HeapSort(int* a, int n, int root)
{
	int end = n - 1;
	int i = 0;
	int j = 0;
	for (j = (end - 1) / 2; j >= 0; j--)
	{
		_HeapSort(a, n, j);//倒着调，每一个都要走一遍
	}
	while (end >= 0)
	{
		for (i = 0; i < n; i++)//输出每一次排的结果
		{
			printf("%d ", a[i]);
		}
		printf("\n");
		Swap(&a[0], &a[end]);//已经排完了，交换
		_HeapSort(a, end, 0);//先排，在减减
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78