数据结构与算法：堆排序
堆排序的基本思想
堆排序的基本思想是将待排序的序列构造成一个大堆或者小堆，此时，整个序列的最大值（最小值）就是堆顶的根节点。将它移走（其实就是将其与数组的末尾元素交换，此时末尾元素就是最大最或最小值），然后将剩余的堆重新构造成一个堆，这样就会得到新的最大值（最小值）。如此反复执行，使能得到一个有序序列了。
具体实现时，首先需要根据给定的待排序数组构建一个初始堆。构建堆的过程通常是从最后一个非叶子节点开始，向上遍历每个节点，对每个节点进行下沉操作，以确保每个节点都满足堆的性质。（向下调整算法） 下沉操作是堆排序中的关键步骤，它通过比较节点与其子节点的值，确保父节点的值大于（对于大堆）或小于（对于小堆）其子节点的值。
在堆构建完成后，堆的根节点就是序列的最大（或最小）元素。将其与堆数组的最后一个元素交换，然后移除最后一个元素（或将其视为已排序部分），此时堆的大小减一。接着，对剩余部分重新进行下沉操作，以恢复堆的性质。这个过程重复进行，知道堆的大小减至1，此时序列已经完全排序。
堆排序的特性总结
- 堆排序使用堆来选数，效率高了很多
- 时间复杂度：
- 空间复杂度：
- 稳定性：不稳定
- 空间效率：堆排序是一种原地排序算法，这意味着它不需要额外的存储空间来辅助排序过程，除了原数组本身。这使得堆排序在处理大数据集时，相较于其他需要额外空间的排序算法，具有更高的空间效率。
- 时间效率：堆排序的时间复杂度在最坏情况下为O(nlogn)，其中n是待排序元素的数量。这意味着无论输入数据的初始状态如何，堆排序都能保持相对稳定的性能。这一点在处理大型数据集时尤为重要，因为某些排序算法（如快速排序）在特定输入情况下可能会退化为O(n²)的时间复杂度。
- 不稳定性：堆排序是一种不稳定的排序算法。这意味着如果两个元素具有相同的值，它们在排序后的相对位置可能会改变。这在某些应用中可能是一个缺点，但在其他不需要保持元素相对位置不变的场景中则不是问题。
代码
#define _CRT_SECURE_NO_WARNINGS
#include "HeapSort.h"
void HeapSort(int* a, int n)
{
//降序，建小堆
//升序，建大堆
向上调整 从数组下标为1的开始调
//for (int i = 1; i < n; i++)
// AdjustUp(a, i);
//向下调整 从第一个非叶子节点开始调
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--;
}
}
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(int* 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(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (a[child + 1] < a[child] && child + 1 < n)
child++;
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}测试
#define _CRT_SECURE_NO_WARNINGS
#include "HeapSort.h"
int main()
{
int arr[] = { 3,1,9,5,7,2,6,4,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, sz);
return 0;
}TopK问题
TopK算法是一种用于找出数据集中前K个最大或最小的元素的算法。它特别适用于处理大量数据，尤其是在内存或处理时间有限的情况下。TopK算法的核心思想是通过维护一个大小为K的堆来高效地找到前K个最大或最小的元素。
堆排序方法：这是实现TopK算法的一种常见方法。首先，使用数据集中的前K个元素建立一个堆（最小堆或最大堆，取决于需要找的是最大还是最小的K个元素）。然后，将剩余的元素逐一与堆顶元素进行比较，如果比堆顶元素大（或小），则替换并调整堆。最终，堆中的元素即为所求的前K个最大（或最小）元素。
//文件中找TOPk
//造数据
void CreateData()
{
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand() + i) % 10000000; //+i 减少重复
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void test1()
{
//CreateData();
//Top k
int k;
scanf("%d", &k);
int* topk = (int*)malloc(sizeof(int) * k);
if (topk == NULL)
{
perror("malloc fail");
return;
}
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//读取文件中的前k个保存到数组中
for (int i = 0; i < k; i++)
fscanf(fout, "%d", &topk[i]);
//建k个数的小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
AdjustDown(topk, k, i);
//读取剩下的 n - k 个数
int x = 0;
while (fscanf(fout, "%d", &x) > 0)
{
if (x > topk[0])
{
topk[0] = x;
AdjustDown(topk, k, 0);
}
}
//排序 向下调整
int end = k - 1;
while (end > 0)
{
Swap(&topk[0], &topk[end]);
AdjustDown(topk, end, 0);
end--;
}
//打印前k个
printf("最大的前%d个：", k);
for (int i = 0; i < k; i++)
{
printf("%d ", topk[i]);
}
}
void test2()
{
int k;
scanf("%d", &k);
int arr[] = { 3,1,9,5,7,2,6,4,8,26538,6707,9105,30541,29850,31600,29234};
int sz = sizeof(arr) / sizeof(arr[0]);
for(int i = (sz - 1 - 1) / 2; i >= 0; i--)
AdjustDown(arr, sz, i);
int end = sz - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
end--;
}
//打印前k个
printf("最大的前%d个：", k);
for (int i = 0; i < k; i++)
{
printf("%d ", arr[i]);
}
}