目录
1>>导言
今天重点内容就是带着大家实现堆排序和Topk，堆排序分为两种，一种是直接调用堆的数据结构来实现的，另一种就是通过堆的思想实现的，Topk就是在一个数组中寻找前k个最大/最小的数，通常利用在世界五百强企业、十大富豪等等。
2>>堆排序
2.1>>通过堆结构实现堆排序
1.首先给了一个数组，我们需要统计出它的大小。
2.创建一个堆结构变量hp，并且初始化它。注意：传的是地址
3.往这个堆中传递arr数组的每个数
4.循环判断，当堆不为空时，每次取根节点，然后删除根节点（删除操作还记得叭？就是讲最后结点和根结点互换，然后size--，就可以将最后一个结点删除，然后将新的根结点向下调整）
5.每次取出的头结点（根据大堆就是最大，小堆就是最小），所以最终就是一个降序/升序啦！
这边以大根堆为结果，宝子们可以去试试噢
2.2>>堆思想实现排序
1.要实现堆排序，首先得要是一个堆，那么第一个循环就要把堆建立，双亲结点向下调整思想，从最后一个结点的双亲结点开始（最后一个结点是n-1)它的双亲结点是-1然后除2，依次向下调整，这样就是一个堆。
2.将这个棵树的每一个子树都想象成一个堆，然后：
3.从最后一个结点开始，到0为止，每次交换它的最后一个结点和第0个结点，然后向下调整，这样就能够从大/从小排序
问题：要实现升序建（大堆/小堆）？要实现降序建（大堆/小堆）？
答案是：升序建大堆，降序建小堆，因为升序每次交换将最大的移到最后面了所以要大堆。
这是最终结果
3>>Topk思想
首先我们来造一个空间为100000的文件，通过之前章节学的随机数初始化文件每个数值
srand表示更改随机数初始值
创建一个file的文件，存放字符指针，叫data.txt
通过fopen打开文件file，w表示写入，若返回不为空则开始往变量fin写数据
最后关闭文件。
上面步骤稍微过一遍，现在开始实现topk，这才是重点：
void TopK()
{
int k = 0;
printf("请输入K：");
scanf("%d", &k);
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
exit(1);
}
//找最大的前K个数，建小堆
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail!");
exit(2);
}
//读取文件中前K个数据建堆
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap[i]);
}
// 建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
adjustdown(minHeap, i, k);
}
//要最大就建小堆，要最小就键大堆
int x = 0;
while (fscanf(fout, "%d", &x) != EOF) {
if (x > minHeap[0]) {
minHeap[0] = x;
adjustdown(minHeap, 0, k);
}
}
for (int i = 0; i < k; i++) {
printf("%d ", minHeap[i]);
}
}输入指定空间/堆大小k，然后读取文件每组数字，要找最大的前k个数，就要建小堆，就跟我们要最大值取最小值min一样的，若返回不为空，那么开始建堆，取前k个数据，建堆，跟建堆思想一样，从最后一个结点的父节点开始，依次向下调整，最后循环遍历文件的每一个数，如果读取到的数数大于我们的根结点，那么另根结点等于它，然后依次向下调整即可
这是文件中的数
4>>代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
void test()
{
HP hp;
hpinit(&hp);
hppush(&hp, 1);
hppush(&hp, 2);
hppush(&hp, 4);
hppush(&hp, 5);
hppop(&hp);
hppop(&hp);
hppop(&hp);
hpdestroy(&hp);
}
void test1() {
int arr[] = { 17,20,10,13,19,15 };
int n = sizeof(arr) / sizeof(arr[0]);
HP hp;
hpinit(&hp);
int i = 0;
for (i = 0; i < n; i++) {
hppush(&hp, arr[i]);
}
i = 0;
while (!hpempty(&hp)) {
arr[i++] = hptop(&hp);
hppop(&hp);
}
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}
void HeapSort(int* arr, int n) {//自己实现堆排序
for (int i =(n-1-1)/2; i >= 0; i--) {
adjustdown(arr, i, n);
}
int end = n - 1;//最后一个结点开始，到0 为止
while (end) {//大根堆
swap(&arr[0], &arr[end]);
adjustdown(arr, 0, end);//end一直--；
end--;
}
//大根堆为升序
}
void CreateNDate()
{
// 造数据
int n = 100000;
srand((unsigned int)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() + i) % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void TopK()
{
int k = 0;
printf("请输入K：");
scanf("%d", &k);
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
exit(1);
}
//找最大的前K个数，建小堆
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail!");
exit(2);
}
//读取文件中前K个数据建堆
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap[i]);
}
// 建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
adjustdown(minHeap, i, k);
}
//要最大就建小堆，要最小就键大堆
int x = 0;
while (fscanf(fout, "%d", &x) != EOF) {
if (x > minHeap[0]) {
minHeap[0] = x;
adjustdown(minHeap, 0, k);
}
}
for (int i = 0; i < k; i++) {
printf("%d ", minHeap[i]);
}
}
int main()
{
/*test();*/
//test1();
//int arr[] = { 17,20,10,13,19,15 };
//int n = sizeof(arr) / sizeof(arr[0]);
//HeapSort(arr, n);
//
//int i;
//for (i = 0; i < n; i++) {
// printf("%d ", arr[i]);
//}
//CreateNDate();
TopK();
return 0;
}#include"heap.h"
void hpinit(HP* php) {
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
bool hpempty(HP* php) {
assert(php);
return php->size==0;
}
int hpsize(HP* php) {
assert(php);
return php->size;
}
void adjustup(hpdatatype* arr, int child) {
//向上调整，parent为（child-1）/2； leftchild为parent*2+1，rightchild为parent*2+2
int parent = (child - 1) / 2;
//为根结点即为0结束
while (child > 0) {
//小根堆<，从上往下每个子孙都比我大
//大根堆>，从上往下每个子孙都比我小
if (arr[child] > arr[parent]) {
//两数交换
swap(&arr[child], &arr[parent]);
//孩子和双亲结点往上走
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void hppush(HP* php, hpdatatype x) {
assert(php);
//空间不够就扩容，与顺序表一致
if (php->size==php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
hpdatatype* tmp = (hpdatatype*)realloc(php->arr, newcapacity * sizeof(hpdatatype));
if (tmp == NULL) {
perror("realloc");
exit(1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
//扩容结束
//存放数据，每次存放就要比较，以小根堆为例子
//0 1 2 3 size为4，新加入的数据下标为size
php->arr[php->size] = x;
//加入的不一定是与祖先比较大的数，因此需要向上调整
adjustup(php->arr, php->size);
//交换完毕size++
php->size++;
}
void adjustdown(hpdatatype* arr, int parent,int size) {
//向下调整，leftchild为parent*2+1，rightchild为parent*2+2
int child = parent * 2 + 1;
//大于等于总结个数n即为size结束
while (child<size) {
//小根堆，从上往下每个子孙都比我大
//大根堆，从上往下每个子孙都比我小
//此时用小根堆
//先要判断左孩子和右孩子哪个更小
if (child + 1 < size && arr[child] > arr[child + 1]) {
child++;
}
//两数交换
//孩子和双亲结点往下走
if (arr[child] < arr[parent])
{
swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void hppop(HP* php) {
assert(php);
assert(!hpempty(php));
//删除堆顶数据不能直接删除
//否则会大乱套
//思路：根屁股结点互换，然后让新的堆顶向下调整,size--
//屁股为size-1；
swap(&php->arr[0], &php->arr[php->size - 1]);
php->size--;
adjustdown(php->arr,0,php->size);
}
hpdatatype hptop(HP* php) {
assert(php);
return php->arr[0];
}
void swap(int* child, int* parent) {
int tmp = *child;
*child = *parent;
*parent = tmp;
}
void hpdestroy(HP* php) {
assert(php);
assert(!hpempty(php));
if (php->arr)
free(php->arr);
php->arr = NULL;
php->size = php->capacity = 0;
}5>>结语
这篇讲的算法思想——堆排序和topk，希望对宝子们有所帮助，有不懂的欢迎评论区指出，也欢迎大佬们指点小编的文章，谢谢大家观看，期待与你下篇再见~
标签：arr,parent,int,堆排序,结点,算法,Topk,child,php From： https://blog.csdn.net/m0_69282950/article/details/143249566