建堆（堆化）与堆排的时间复杂度和空间复杂度的推导及TopK问题_堆排序找出前k个最小值时间复杂度

一：建堆
第一种情况：时间复杂度O（logn）
若左右子树恰好都是小堆，如何建小堆呢？

算法：向下调整算法
1.

	选出孩子中小的那一个
1

a）小的孩子跟父亲相比，比父亲小则与父亲交换，并把原来孩子的位置当成父亲的新位置继续往下调整，直到
parent走到叶子节点
b）若比父亲大则不需要处理，调整完成，整个树已经是小堆。
1
2
3

//向下调整算法

void Swap(int* a, int* b)
{
   
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
   
	int child = 2 * parent + 1;
	while (child < n)
	{
   
		if (a[child] > a[child + 1] && child + 1 < n)  //建小堆
		//if (a[child] < a[child + 1] && child + 1 < n)  //建大堆
		{
   
			child++;
		}
		if (a[child] < a[parent])	//小堆
		//if (a[child] > a[parent]) //大堆
		{
   
			Swap(&a[child], &a[parent]);
			parent 
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