时间复杂度为O(N)的建堆方法分析+代码

1. 建堆操作：

方法1：边插边调，时间复杂度为O(NlogN)

分析：
每个节点插入过程中，不论是向上还是向下，时间复杂度logN。总共N个节点，所以是NlogN。

方法2：插完再调，最优时间复杂度为：O(N)。

---

分析：（以满二叉树为例）
当插完后，深度为h。
如果采用向上调整，从最后一层开始：
最后一层共2^(h-1)个节点，每个节点按最坏（时间复杂度分析都是按最坏）需要调整h-1次。
再往上走，
而第二层，2个节点，调整1次。所以总共：
T(N) = 2*1 + 2^2 2 + 。。。+ 【2^(h-1)】(h-1) = NlogN，这里不细致写了。

---

如果采用向下调整，从倒数第二层的最后一个父节点开始，对整个堆向下调整。
以倒数第二层为例，有2^（h-2）个节点。为当前局部的堆有序，只需调1次就行。
而第一层1个节点最坏需要调整h-1次，因为每次向下都是从当前点到子节点。
T(N) = 2^(h-2)1 + 。。。+ 1 (h-1) = O(N)

总之计算啥都是错位相减法。

代码

TOPK：求N数中最大K个

算法步骤：

1. 从N个数中的前K个建小根堆：从最后一个父节点，下标为【(k-2)/2】位起到0号位置节点，做总父节点次向下调整，每次向下调整时间复杂度为O(logN)，这样就建好k小根堆。

分析1：直接操作数组时，我们默认现在初始化号了堆，因为上面分析了先放数据，再利用从小爹到根节点次向下调整，时间复杂度最佳为O(N)。此外，这里如果从下标k-1处开始做向下调整，也能，但是没必要，且这样达不到O(N)，上面分析过，这个错误不能犯。
代码如下:

for (int i = (k-2)/2; i >= 0; i--)
	{
		// 爹在i，从0开始向下调整
		AdjustDown(a, k, i);
	}
1
2
3
4
5

(注意一定是做从K-2/2位置减到0次且每次都以当前i为父的向下调整。)

2. 剩余N-K个数，依次去和小根堆堆顶比较，若大于堆顶则交换，然后adjust整体。这样一来，由于开始是小根堆，但凡大于它的，都会去顶上，且如果不大于堆顶更不会大于它的子节点处。

分析2：利用小根堆的原因就是这样的做法建堆小，能实现取topK。如果用大根堆，N过大，内存存放不下，不能操作。

全部代码：（模拟该算法，并非N很大，N很大利用文件操作的代码在最下面）
【这里想再分析一下adjust向下调整】：接收的参数是堆大小size、父位置parent。
首先，因在做从parent向最小孩的向下调整，所以

1. 求孩子，2*p+1,【这是左孩子】
2. 在有左孩子的前提下【while(min_child
3. 向下调整的核心：当栈顶大于【较小的】孩子，就交换。但是如果不大，直接停止，因为这一部分不需要调整，因为已经符合了堆的逻辑结构。

// 对n个数，从父位置parent向下调整
// 向下调整找较小，且这里做小根堆，找较小
// 从爹向下调整，要找child中较小值，默认求左孩子，右孩子
// 循环条件是写左孩子一直存在 现在先建小根堆，所以拿小值
// 小于就交换
// 向下走
void AdjustDown(int* a, int n, int parent)
{
	int min_child = parent * 2 + 1;
	while (min_child < n)
	{
		if (min_child + 1 < n && a[min_child+1]<a[min_child])
		{
			min_child++;
		}

		if (a[parent]>a[min_child])
		{
			Swap(&a[parent], &a[min_child]);
		}
		else
		{
			break;
		}
		parent = min_child;
		min_child = parent * 2 + 1;
	}
}
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

// k个值建堆
// 所谓先建堆，再调整，这里相当于堆好了
// 注意些出来：初始建堆一定是从0开始：parent
void heapsort(int* a, int k, int N)
{
	int val;
	// i = 1:55 66 100
	// i = (k-2)/2 :55 66 100
	// 步骤一：建堆
	for (int i = (k-2)/2; i >= 0; i--)
	{
		// 从i做向下调
		AdjustDown(a, k, i);
	}
	// 取后N-K个做比较
	for (int i = k; i < N; i++)
	{
		if (a[0] < a[i])
		{
			val = a[i];
			Swap(&a[0], &val);
			// 做从0往下的调整
			AdjustDown(a, k, 0);
		}
	}
	for (int i = 0; i < k; 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

注意：以上代码用了两次向下调整，但是不一样，第一次规范堆时候，做以i为根的向下调整，而后面比较N-K时的向下调整都以0为根，因此时堆已建好，需时刻规范以0为顶的堆

PS： 说三遍：建堆和调整时的向下调整parent不一样哦

PS： 说三遍：建堆和调整时的向下调整parent不一样哦

PS： 说三遍：建堆和调整时的向下调整parent不一样哦

---

---

---

---

真实情况：N较大，数值均存在文件中的TOPK求法

解释：当N过大，内存放不下，我们所有数据均从文件中读，最后再写入文件中。
代码如下：

void PrintTopK(const char* filename, int k)
{
	assert(filename);
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror(NULL);
		return;
	}
	int* minHeap = (int*)malloc(sizeof(int)*k);
	// 如何拿前K个：文件读写如何读：读写整数最好用fprintf fcanfs
	// 它们的特点是可以像去f去s之后用，只是操作对象不同，是文件
	// 读前K
	for (int i = 0; i < k; ++i)
	{
		// 没有给空格，但是能读到数据，txt文件中虽然以空格分隔。
		// 因为scanf会默认忽略空格和换行，自动认为数之间以这些分隔开了
		fscanf(fout, "%d", &minHeap[i]);
		printf("当前读入了%d\n", minHeap[i]);
	}
	// 博客写这一段即可
	// 建堆：向下调整建堆  -1是k个数最后一个的下标,因为以k个数字建堆，k-1是最后一个，-1/2是爹，用先插的方法向下建堆，复杂度O(n) 
	// 可是这里建堆利用向下，起来的是小堆吗？
	for (int j = (k-2)/2;j >= 0; j--)
	{
		AdjustDown(minHeap, k, j);	// k个数的小堆，j是父亲位置，以前是0是因为在pop后换上最后一个再向下调整
	}

	// 再拿后N-K个：直接读完即可
	int val = 0;
	while (fscanf(fout, "%d", &val)!=EOF)
	{
		printf("现在比较的是%d\n", val);

		if (minHeap[0] < val)
		{
			// 赋值给它
			minHeap[0] = val;
			printf("改了\n");
			// 还要向下调整，不然不是小堆了：重新辨析down的参数：堆、size、parent（因为向下，肯定从输入爹位置）
			AdjustDown(minHeap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}

	fclose(fout);

}

// 把k个数字写到文件中去
void CreateDataFile(const char* filename, int N)
{
	FILE* fin = fopen(filename, "w");
	if (fin == NULL)
	{
		perror("fopen fin fail\n");
		return;
	}
	srand(time(0));
	for (int i = 0; i < N; i++)
	{
		// 注意写入这里加入空格，或者换行符做分隔符都可以，rand是固定写法
		fprintf(fin, "%d\n", rand());
	}
	fclose(fin);

}

int main()
{
	const char* filename = "Data.txt";
	int N = 1000;
	int k = 3;
	//CreateDataFile(filename, N);
	PrintTopK(filename, k);
	// 如何知道自己的前K个是正确的 写个取模：让数字最大是某个值，然后自己打开文件随便给文件中加入更大的值，最后看结果是不是你写进去的那几个数字。

	return 0;
}
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

代码分析：

1. 读文件：从文件中读fscanf：默认会以空格或换行符分隔然后读数据，给一个数字的地址，给文件指针，就可以把数据读到数组中。读到数组中后，【和上面的一样】利用向下调整，从最后一个父到0，做每次有k个数、每次从当前父位的向下调整，造一个有k个值的小根堆。
2. 将k个值写入文件：利用fprintf和随机时间种子把随机数据写入文件。以fprintf写数据可以以\n和空格作为分隔符。

代码总体思路就是：利用文件写方式，生成一个N值文件，然后利用堆排序选TOPK。