2024-1-26学习任务：堆实现算法和topK问题

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
//向上调整
void Adjustup(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int size, int parent);
//堆排序
void HeapSort(int* a, int n);

void Adjustup(HPDataType* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;//求二叉树父亲结点的方法
	while (child > 0)
	{
		if (a[parent] < a[child])//父亲结点的值小于孩子就交换（大堆
		{
			Swap(&a[parent], &a[child]);//简单的交换函数（自己定义即可）
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}

}

void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;//根据孩子求父亲
	while (child < size)
	{
		if (child+1<size&&a[child]<a[child+1])//假设法，假设第一个孩子最大，如果下一个孩子不越界的情况比它还大，就++
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
		
	}

}

void HeapSort(int* a, int n)
{
	for (int i=(n-2)/2;i>=0;i--)
	{
		//建堆
		AdjustDown(a, n,i);//采用向下调整算法进行建堆
	}
	int end = n - 1;//从数组的最后一个数开始，n-1就是
	while (end > 0)
	{
		Swap(&a[0], &a[end]);//交换函数
		AdjustDown(a, end, 0);
		--end;//每次调整完后，end--
	}
}

void CreateNDate()
{
	// 造数据
	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() + i) % 100000;//求随机数函数
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void PrintTopK(const char* file, int k)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	// 建一个k个数小堆
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}

	// 读取前k个，建小堆
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
		Adjustup(minheap, i);
	}

	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])//与栈顶元素交换
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);//同时向下调整
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	free(minheap);
	fclose(fout);
}

void HeapSort(int* a, int n)
{
	for (int i=1;i<n;i++)
	{
		//建堆
		Adjustup(a, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

void HeapSort(int* a, int n)
{
	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;
	}
}