堆和堆排序

1.二叉树的顺序存储

顺序存储就是数组存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间上的浪费。在现实生活中，只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.堆的性质

小堆

堆是一棵完全二叉树
堆的父亲节点总是小于孩子节点
根节点最小

大堆

堆是一棵完全二叉树
堆的父亲节点总是大于孩子节点
根节点最大

3.堆的实现

3.1 堆的插入（向上调整算法）

方法：

1.先将元素插入到堆的末尾，即最后一个孩子处
2.插入后如果堆的性质遭到破坏，将新插入节点顺着双亲往上调整

时间复杂度：O（NlogN)

举例：先插入一个20到堆的末尾，再往上进行调整算法，直到满足堆

举例：先插入一个10到堆的末尾，再往上进行调整算法，直到满足堆

void Adjustup(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.2 堆向下调整算法

现在我们给出一个数组，逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

前提：左右子树必须是一个堆，才能调整
时间复杂度：O（N）

int a[]={27,15,19,18,28,34,65,49,25,37};

void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设法：假设左孩子比右孩子小
	//求左孩子的下标
	int child = parent * 2 + 1;
	while (child<n)
	{
		if (child + 1 < n && a[child] > a[child + 1])//左孩子比右孩子大
		{
			++child;
		}
		
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.3 堆的创建

下面我们给一个数组，这个数组逻辑上可以看成一棵完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。

根节点左右子树不是堆，我们怎么调整呢？

方法一：向下调整法
我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的数，就可以调整成堆
方法二：向上调整算法
我们把数组第一个元素看成是堆，然后利用循环构建堆

int a[]={ 4,2,8,1,5,6,9,7,2,7,9 };

向下调整算法

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(a, n, i);
}
1
2
3
4

向上调整算法

for (int i = 1; i < n; i++)
{
	Adjustup(a, i);
}
1
2
3
4

3.4 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。

3.5 全套代码

#include 
#include 
#include 
#include 

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

void HPInint(Heap* hph);//初始化
void HPDestroy(Heap* hph);//销毁
void HPPush(Heap* hph, HPDataType x);//插入
void HPPop(Heap* hph);//删除
HPDataType HPTop(Heap* hph);//取堆顶元素
bool HPEmpty(Heap* hph);//判空
int HeapSize(Heap* hp);//求个数

void Adjustup(HPDataType* a, int child);//向上调整算法
void swap(HPDataType* p1, HPDataType* p2);//交换
void AdjustDown(HPDataType* a, int n, int parent);//向下调整算法

#include "Heap.h"

void HPInint(Heap* hph)
{
	assert(hph);
	hph->a = NULL;
	hph->capacity = hph->size = 0;
}

void HPDestroy(Heap* hph)
{
	assert(hph);
	free(hph->a);
	hph->a = NULL;
	hph->capacity = hph->size = 0;
}

void swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//时间复杂度：NlogN
void Adjustup(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


void AdjustDown(HPDataType* a, int n, int parent)
{
	//求左孩子的下标
	int child = parent * 2 + 1;
	//假设法：
	while (child<n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}

void HPPush(Heap* hph, HPDataType x)
{
	assert(hph);
	//扩容
	if (hph->capacity == hph->size)
	{
		int newcapacity = hph->capacity == 0 ? 4 : hph->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hph->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//扩容成功
		hph->a = tmp;
		hph->capacity = newcapacity;
	}
	hph->a[hph->size] = x;
	hph->size++;

	//向上调整
	Adjustup(hph->a, hph->size - 1);
}

void HPPop(Heap* hph)
{
	assert(hph);
	assert(hph->size > 0);
	swap(&hph->a[0], &hph->a[hph->size - 1]);
	hph->size--;

	//向下调整
	AdjustDown(hph->a, hph->size, 0);
}

HPDataType HPTop(Heap* hph)
{
	assert(hph);
	assert(hph->size > 0);
	return hph->a[0];
}
bool HPEmpty(Heap* hph)
{
	assert(hph);
	return hph->size == 0;
}

int HeapSize(Heap* hph)
{
	assert(hph);
	return hph->size;
}
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

4.堆排序

堆排序是利用堆积树这种结构所设计的一种排序的算法，它是选择排序的一种。

排升序建大堆
排降序建小堆
时间复杂度：O（Nlog N）

void HeapSort(int* a, int n)
{
	//建堆
	//升序，建大堆
	降序，建小堆
	
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//建堆完成
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.Top-K问题

求数据结合中前k个最大的元素或者最小的元素，一般情况下数据量都比较大。
eg：专业前10名，世界500强等
对于top-k问题，能想到最简单的问题就是排序，但是：如果数据量非常大，排序就不可取了（可能数据都不能一下子全部加载到内存中）。最佳的方式就是用堆来解决

• 用数据集合中前k个元素建堆
  • 前k个最大元素，建小堆
  • 前k个最小元素，建大堆
• 用剩余的N-K个元素一次与堆顶元素相比较，不满足则替换堆顶元素

void PrintTopK(int* a, int n, int k)
{
	//升序，建大堆
	//降序，建小堆
	
	// 1. 建堆--用a中前k个元素建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, k, i);
	}

	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则替换
	for (int i = k ; i < n; i++)
	{
		if (a[i] > a[0])
		{
			a[0] = a[i];
			AdjustDown(a, k, 0);
		}
	}

	int end = k - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
	
	//打印前k个最大的数
	for (int i = 0; i < 5; i++)
		printf("%d ", a[i]);
}
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