【数据结构】《自此，每一个想考我堆排序（Top-k问题）的面试官，下场都很尴尬【附完整代码实现】》

//定义堆结构
typedef int HPDataType;
typedef struct Heap 
{
	HPDataType* arr;
	int size;    //有效数据个数
	int capaicty;//空间大小
}HP;

#include "Heap.h"

//初始化
void HpInit(HP* php)//也是，要改变指向的对象，取地址
{
	assert(php);
	php->arr = NULL;
	php->size = php->capaicty = 0;
}

#include"Heap.h"
void HPDesTroy(HP* php)
{
	assert(php);
	if (php->arr)
		{
            free(php->arr);
        }
	php->arr = NULL;
	php->size = php->capaicty = 0;
}

#include "Heap.h"
//交换父子算法
void Swap(int* x, int* y)//传的是地址，解引用
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	//求父亲
	int parent = (child - 1) / 2;

	//当child为头节点时，没有父节点，结束
	while (child > 0)
	{
		//建大堆条件：>
		//建小堆条件: <
		//这里是大堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

//打印堆
void HPPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->arr[i]);
	}
	printf("\n");
}

Heap.c
#include "Heap.h"
//入堆
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//空间不够要增容
	if (php->size == php->capaicty)
	{
		//增容
		int newCapacity = php->capaicty == 0 ? 4 : 2 * php->capaicty;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capaicty = newCapacity;
	}
	//空间足够
	php->arr[php->size] = x;

	//向上调整
	AdjustUp(php->arr, php->size);
	++(php->size);
}

test.c
#include "Heap.h"

void test01()
{
	HP hp;
	//初始化
	HPInit(&hp);
	HPPush(&hp, 25);
	HPPush(&hp, 15);
	HPPush(&hp, 10);
    //插入80
	HPPush(&hp, 80);
	//打印
	HPPrint(&hp);
	//销毁
	HPDesTroy(&hp);

}

int main()
{
	test01();
	return 0;
}

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)//传父节点下标、有效数据个数
{
	int child = parent * 2 + 1;

	//下面统一以大堆示范
	while (child < n)//child超过n，代表没有子节点了
	{
		//大堆结构：<，小堆结构: >
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}

		//孩子和父亲比较
		//大堆结构：>，小堆结构:<
		if (arr[child] > arr[parent])
		{
			//父子调换
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else 
		{
			break;
		}
	}
}

Heap.c
#include "Heap.h"

//出堆（堆顶）
void HPPop(HP* php)
{
	assert(!HPEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	--(php->size);

	//堆顶数据向下调整
	AdjustDown(php->arr, 0, php->size);
}

test.c
#include "Heap.h"

void test01()
{
	HP hp;
	//初始化
	HPInit(&hp);
	//入堆
	HPPush(&hp, 25);
	HPPush(&hp, 15);
	HPPush(&hp, 10);
	HPPush(&hp, 80);
	//打印
	HPPrint(&hp);
	//出堆
	HPPop(&hp);
	HPPrint(&hp);
	HPPop(&hp);
	HPPrint(&hp);
	HPPop(&hp);
	HPPrint(&hp);

	//销毁
	HPDesTroy(&hp);
}

int main()
{
	test01();
	return 0;
}

Heap.c
#include "Heap.h"

//取堆顶
HPDataType HPTop(HP* php)
{
	assert(!HPEmpty(php));
	return php->arr[0];
}

test.c
#include "Heap.h"

//循环取堆顶
while (!HPEmpty(&hp))
{
	int top = HPTop(&hp);
	printf("%d ", top);
	HPPop(&hp);
}

test.c

//假的堆排序--使用的是数据结构--堆
void HeapSort01(int* arr, int n)
{
	HP hp;//使用堆结构
	HPInit(&hp);

	//将乱序数值放入堆中
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, arr[i]);
	}

	//取堆顶，输出升序或降序
	int i = 0;
	while (!HPEmpty(&hp))//直到堆为空
	{
		int top = HPTop(&hp);
		arr[i++] = top;//将有序的数值存入数组
		HPPop(&hp);
	}
	HPDesTroy(&hp);
}



int main()
{
	int arr[6] = { 30,56,25,15,70,10 };
	printf("排序之前：\n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	HeapSort01(arr, 6);
	printf("排序之后：\n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

//冒泡排序--时间复杂度O（N^2）
void BubbleSort(int* arr, int n)
{
	for (int i= 0; i < n; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				exchange = 1;
				Swap(&arr[j], &arr[j + 1]);
			}
		}

		if (exchange = 0)
		{
			break;
		}
	}

}

//真的堆排序
//堆排序————使用的是堆结构的思想
void HeapSort(int* arr, int n)
{

	//向下调整算法——建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	//实现排序--升序数组
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);//logn
		end--;
	}
}

int main()
{
	//test01();

	int arr[6] = { 30,56,25,15,70,10 };
	printf("排序之前：\n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	HeapSort(arr, 6);
	printf("排序之后：\n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

void CreateNDate()
{
	// 造数据
	int n = 100000;
	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) % 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 fail!");
		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]);
	}
	//数组调整建堆--向下调整建堆
	//找最大的前K个数，建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);
	}
	//遍历剩下的n-k个数，跟堆顶比较，谁大谁入堆
	int data = 0;
	while (fscanf(fout, "%d", &data) != EOF)
	{
		if (data > minHeap[0])
		{
			minHeap[0] = data;
			AdjustDown(minHeap, 0, k);
		}
	}

	//打印堆里的数据
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");

	fclose(fout);
}

int main()
{
	//CreateNDate();
	TopK();
	return 0;
}