堆排序

堆排序是一种基于堆数据结构的排序算法。它的基本思想是，将待排序的序列构建成一个大根堆（或小根堆），然后依次取出堆顶元素（即最大值或最小值），将其放入已排序序列的末尾，再将剩余的元素重新调整为一个新的堆。重复这个过程，直到所有元素都被取出并放入已排序序列中。

具体来说，堆排序的过程如下：

将待排序的长度为n序列构建成一个大根堆（或小根堆）。这个过程可以从最后一个非叶子节点开始，依次向前进行，保证每个子树都是一个大根堆（或小根堆）。
取出堆顶元素（即最大值或最小值），将其放入已排序序列的末尾。
将剩余（n-1）的元素重新调整为一个新的堆。
重复步骤 2 和步骤 3，直到所有元素都被取出并放入已排序序列中。最终得到的序列就是排好序的。

最终得到的序列就是排好序的。

堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

在这里插入图片描述

向下调整法

从非叶节点的最后一个数据的下标开始，每次取出孩子中较大或较小的数（看是大堆还是小堆）向下进行调整，由于每多一层，下层是上层的二倍，这种办法直接可以省略掉最后一层，也可以达到建堆的目的，所以这种办法为更优的办法。

由于需要向下调整，所以这种办法需要找到子节点，我们已经知道父结点的运算了，子结点就是父节点的逆运算。

结合上面所说，实现代码如下：

void AdjustDown(HeapDataType* arr, int n, int parent)//向下调整
{
	assert(arr);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child<n - 1 && arr[child] > arr[child + 1])
		{
			child = child + 1;
		}
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
		}
		parent = child;
		child = child * 2 + 1;
	}
}

void HeapSort(int* a,int n)//堆排序
{
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n,i);
	}

	for (int i = n-1; i > 0; i--)
	{
		swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	int arr[] = { 1,4,6,2,4,8,5,8,3,111,4,5,32,44 };
	HeapSort(arr, sizeof(arr) / sizeof(int));
}

Top-k问题

Top-k 问题是指在一个数据集中找到前 k 个最大（或最小）的元素。一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

下面是使用堆排序实现 Top-k 问题的具体步骤：

创建一个大小为 k 的小根堆，用于存储当前的前 k 个最大元素。
将前 k 个元素插入小根堆中。
遍历剩余的元素，对于每个元素执行以下操作：
- 如果当前元素比堆顶元素大，则将堆顶元素弹出，再将当前元素插入堆中。
遍历完所有元素后，小根堆中剩余的 k 个元素就是前 k 个最大元素。

使用堆排序实现 Top-k 问题的时间复杂度为 O(nlogk)，空间复杂度为 O(k)，其中 n 是数据集的大小。这种方法适用于数据集较大的情况，但需要额外的空间来存储堆。

代码实现

生成一个有10000随机数的文件

void CreateNDate()	//生成一个有10000个随机数的文件
{
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = rand() % 10000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

按上述步骤进行排序

void AdjustDown(HeapDataType* arr, int n, int parent)//向下调整
{
	assert(arr);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child<n - 1 && arr[child] > arr[child + 1])
		{
			child = child + 1;
		}
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
		}
		parent = child;
		child = child * 2 + 1;
	}
}
void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fin = fopen(file, "r");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	int* heap = (int*)malloc(k * sizeof(int));
	int x;
	for (int i = 0; i < 5; i++)
	{
		fscanf(fin,"%d",&heap[i] );//将前k个元素放到数组里
	}
    for (int i = (k - 1 - 1) / 2; i >= 0; i--)	//将k个元素建立一个小堆
	{
		AdjustDown(heap, k, i);
	}
	while (!feof(fin))
	{
		fscanf(fin, "%d", &x);
		if (heap[0] < x)
		{
			heap[0] = x;		//将剩余n-k个元素依次与堆顶元素交换，不满则则替换

			AdjustDown(heap,k,0);
		}
	}
	fclose(fin);
	for (int i = 0; i < k; i++)
	{
		printf("%d  ", heap[i]);
	}
}

int main()
{
	CreateNDate();
	PrintTopK(10);
}