目录

 堆的建立

 向上调整建堆 

向下调整建堆 

向上调整和向下调整时间复杂度的比较 

大小堆如何选择 

Top-K问题 

之前我们实现的堆是创建一个数组，将元素组的内容拷贝过来进行排序的，这样的空间复杂度是O(N)，我们可对堆进行优化，使得不拷贝元素，直接在原数组上进行操作使得原数组变为有序的数组

 堆的建立

 向上调整建堆 

堆排序代码加详细注释，史上最全的堆排序注释

txt 0星 超过10%的资源 2KB

下载

//建堆——向上调整建堆 第一个元素看作一个堆，后面的元素看作依次插入
	for (int i = 1; i < n; ++i)
	{
		AdjustUp(a, i);
	}

向下调整建堆 

之前向下调整的建堆方法是，头尾交换然后将头向下调整，向下调整的前提是左右子树都是大堆或小堆

当数组是这个样子。就无法使用向下调整 

我们可以从倒数第一个非叶子节点（倒数第一个叶子节点的父节点）开始向下开始调，直到调整到根，叶子节点没必要调（兄弟关系），

 先让i指向60，然后60和70交换，i--，i指向100再进行调整，之后再i--，i等于100进行调整

	//建堆——向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点
		//物理上操作数组，逻辑上在操作堆
	{
		AdjusuDown(a, n, i);
	}

向上调整和向下调整时间复杂度的比较 

向下调整时间复杂度：O（N）

 向下调整总步数=该层个数*需向下调整次数

 当满二叉树节点较多时，最后一层节点的个数约为总结点个数的一半，向下调整的好处：节点所在层数越小（以第1层为比较基准），调整次数越多，节点所在层数越大，此时节点越多，调整次数越小

 向上调整时间复杂度：O(N*logN)

 

 利用错位相减可计算出调整次数

我们只算最后一层的调整次数

 

 向上调整：越往下节点越多，调整次数越多，算法时间复杂度过大

大小堆如何选择 

 对于升序和降序我们该如何选择建堆方式？

答案：1.升序——大堆     2.降序——小堆

大思路：选择排序，依次选数，从后往前排

升序建小堆会出问题

 

 建堆的时间复杂度是O(N)，效率低

 选数

	
	//选数
	int i = 0;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjusuDown(a, n - i, 0);
		++i;
	}

void AdjusuDown(HPDataTypedef* a,int n, HPDataTypedef parent)
{
	HPDataTypedef minChild = parent * 2 + 1;
	while (minChild
	{
		if (minChild+11] >a[minChild])
		{
			minChild++;
		}
		if (a[minChild] > a[parent])
		{
			Swap(&a[parent], &a[minChild]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
			break;
	}
}
void Heapsort(int* a, int n)
{
	//建堆——向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点
		//物理上操作数组，逻辑上在操作堆
	{
		AdjusuDown(a, n, i);
	}
	//选数
	int i = 1;
	while (i < n)
	{
		Swap(&a[0], &a[n - i]);
		AdjusuDown(a, n - i, 0);
		++i;
	}
}
int main()
{
	int a[] = { 65,100,75,32,50,60 };
	Heapsort(a, 6);
	return 0;
}

Top-K问题 

 TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素
找前K个最大的

1.排序——O(N*logN)

2.堆选数

  a.建大堆和建小堆都可以，建大堆相当于选K次（Pop k次）时间复杂度：O(N+logN*k)

 更好的方式，建小堆

1.用前K个数，建K个数的小堆

2.依次遍历后续的N-k个数，如果比堆里的数据大，就替换堆里的数据，然后向下替换

，堆里的数据就是最大的前K个

时间复杂度：K+logK*（N-K），综合之后O(N)，空间复杂度O（K）

以文件方式进行操作(这里数组大小为10，K=10)

void PrintTopK(const char* filename, int k)
{
	assert(filename);
 
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
 
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail");
		return;
	}
	// 如何读取前K个数据
	for (int i = 0; i < k; ++i)
	{
		fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行
	}
 
	// 建k个数小堆
	for (int j = (k - 2) / 2; j >= 0; --j)
	{
		AdjusuDown(minHeap, k, j);
	}
 
	// 继续读取后N-K
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			AdjusuDown(minHeap, k, 0);
		}
	}
 
	for (int i = 0; i < k; ++i)
	{
		printf("%d ", minHeap[i]);
	}
 
	free(minHeap);
	fclose(fout);
}
 
int main()
{
	const char* filename = "Data.txt";
	int N = 10000;
	int K = 10;
	//CreateDataFile(filename, N);
	PrintTopK(filename, K);
 
	return 0;
}

void CreateDataFile(const char* filename, int N)
{
	FILE* fin = fopen(filename, "w");
	if (fin == NULL)
	{
		perror("fopen fail");
		return;
	}
	srand(time(0));
 
	for (int i = 0; i < N; ++i)
	{
		fprintf(fin, "%d\n", rand() % 1000000);
	}
 
	fclose(fin);
}
void PrintTopK(const char* filename, int k)
{
	assert(filename);
 
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		perror("fopen fail");
		return;
	}
 
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail");
		return;
	}
	// 如何读取前K个数据
	for (int i = 0; i < k; ++i)
	{
		fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行
	}
 
	// 建k个数小堆
	for (int j = (k - 2) / 2; j >= 0; --j)//（k-1-1）/2
	{
		AdjusuDown(minHeap, k, j);
	}
 
	// 继续读取后N-K
	int val = 0;
	while (fscanf(fout, "%d", &val) != EOF)
	{
		if (val > minHeap[0])
		{
			minHeap[0] = val;
			AdjusuDown(minHeap, k, 0);
		}
	}
 
	for (int i = 0; i < k; ++i)
	{
		printf("%d ", minHeap[i]);
	}
 
	free(minHeap);
	fclose(fout);
}
 
int main()
{
	const char* filename = "Data.txt";
	int N = 10000;
	int K = 10;
	CreateDataFile(filename, N);//
	PrintTopK(filename, K);
 
	return 0;
}