《数据结构初阶》【堆 + 堆排序 + TOP-K】

typedef int HPDataType;
typedef struct Heap
{
	//核心思路：堆是完全二叉树所以使用数组实现比较好
	
	//1.记录数组的容量 ---> 一个int变量
	//2.记录当前数组中元素的数量 --> 一个int变量
	//3.使用数组存储堆中的节点 ---> 定义一个动态数组
	int capacity;
	int size;
	HPDataType* a;
	
}HP;

---------------------------------Heap.h---------------------------------
#pragma once

//任务1：声明需要使用的头文件
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>


//任务2：定义堆的结构体（存储类型）
typedef int HPDataType;
typedef struct Heap
{
	//核心思路：堆是完全二叉树所以使用数组实现比较好
	
	//1.记录数组的容量 ---> 一个int变量
	//2.记录当前数组中元素的数量 --> 一个int变量
	//3.使用数组存储堆中的节点 ---> 定义一个动态数组
	int capacity;
	int size;
	HPDataType* a;
	
}HP;


//任务3：声明堆的常用的工具函数
//1.交换数组中两个元素
//2.堆的向上调整算法（用于插入元素后维护堆的性质）
//3.堆的向下调整算法（用于删除元素后维护堆的性质）

void Swap(HPDataType* a, HPDataType* b);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int parent, int n);

//注意：这里我们使用的这些工具函数的形参不是：堆，；而是：动态数组
//原因：传参时传入动态数组是因为这些工具函数不仅可以用在实现“堆”这种的数据结构上，还可以继续使用在“堆排序”上

//任务4：声明堆的接口
//1.堆的初始化
//2.堆的销毁

//3.堆的插入
//4.堆的删除

//5.堆的取出堆元素
//6.堆的判空

void HPInit(HP* php);
void HPDestroy(HP* php);

void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);

HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);

--------------------------------Heap.c--------------------------------
    
#include "Heap.h"

//1.实现：“交换两个元素的值”工具函数
void Swap(HPDataType* a, HPDataType* b)//形参是是指针类型，函数中的修改会影响到原数组中的值
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}


//2.实现：“向上调整算法”工具函数
void AdjustUp(HPDataType* a, int child)
{
	//1.计算出父节点在数组中的下标（我们有孩子 ---> 得到双亲）
	int parent = child - 1 >> 1;

	//2.接下来不断的进行向上调整，何时调整结束？ ---> 回答：1.当孩子已经调整成根节点时 2.当孩子不满小堆的性质时（这里我们模拟小根堆）
	while (child > 0)
	{
		//3.使用if-else语句进行小根堆的条件检查（小根堆：谁小谁当爹）
		if (a[child] >= a[parent]) return;
		else
		{
			//4.1：交换的孩子节点和双亲节点的值
			Swap(&a[child], &a[parent]);
			//4.2：更新孩子的索引 ---> 因为我们要为孩子找到一个合适的位置
			child = parent;
			//4.3：求出现在孩子的双亲节点的索引
			parent = child - 1 >> 1;
		}
	}
}



//3.实现：“向下调整算法”工具函数
void AdjustDown(HPDataType* a, int parent, int n)
{
	//1.计算出孩子节点在数组中的下标（我们有双亲节点 --->  得到“值最小的”孩子）
	//这里和向上调整有点不一样：找双亲节点就只有一个，但是找孩子节点有两个，要找哪一个呢？---> 找值最小的孩子

	//注：这里使用假设法：假设双亲的左孩子是最小的孩子
	int minchild = parent << 1 + 1;

	//2.接下来不断地进行向下调整，何时调整结束 --->  1.当孩子节点的索引已经大于数组的容量，即：孩子不存在时 2.当孩子不满足小根堆的条件检查时
	while (minchild < n)
	{
		//3.调整出minchild代表是最小的孩子
		if (minchild + 1 < n && a[minchild] > a[minchild + 1])
		{
			minchild++; //切换到右孩子
		}

		//3.使用if-else语句进行小根堆的条件检查
		if (a[minchild] >= a[parent]) return;
		else
		{
			//4.1：交换孩子节点和双亲节点的值
			Swap(&a[minchild], &a[parent]);
			//4.1：更新双亲节点的索引
			parent = minchild;
			//4.2：求出现在双亲节点的孩子节点的索引
			minchild = parent << 1 + 1;
		}
	}

}

//--------------------------------------------------------------------------------------------------------------------------------------

//1.实现：“堆的初始化”操作
void HPInit(HP* php)
{
	assert(php);

	php->capacity = 0;
	php->size = 0;
	php->a = NULL;

}


//2.实现：“堆的销毁”操作
void HPDestroy(HP* php)
{
	assert(php);

	php->capacity = 0;
	php->size = 0;
	free(php->a);
	php->a = NULL;
}


//3.实现：“堆的插入”操作
void HPPush(HP* php,HPDataType x)
{
	assert(php);

	//1.插入操作要先判断：isfull + 选择进行扩容
	if (php->size == php->capacity)
	{
		//1.1进行扩容:(扩容可能有两种情况：1.我们没有分配空间进行扩容 2.我们现在的空间不足进行的扩容)
		//1.1.1:先判断一下我们是因为哪种情况才进行扩容的
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		//1.1.2：realloc新的内存空间
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));

		//1.2.判断空间是否分配成功
		if (tmp == NULL)
		{
			perror("realloc fail");
		}

		//1.3.更新动态数组的内存空间
		php->a = tmp;
		//1.4.更新动态数组的容量
		php->capacity = newCapacity;
	}

	//2.1.将元素插入到数组的末尾
	php->a[php->size] = x;
	//2.2.更新动态数组的容量
	php->size++;


	//3.向上调整新插入的元素
	AdjustUp(php->a, php->size - 1);// 注意：向上调整算法的第二个形参是“孩子在数组中的索引”
}


//4.实现：“堆的删除”操作
void HPPop(HP* php)
{
	assert(php);
	///0.删除元素要先判断堆中是否还有元素
	assert(php->size > 0);

	//1.将堆顶的元素与末尾的元素进行交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	//2.更新动态数组的容量-->删除堆末尾的元素
	php->size--;
	//3.从堆顶开始向下调整
	AdjustDown(php->a, 0, php->size);
}


//5.实现：“堆的取堆顶元素”操作
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

//6.实现：“堆的判空”操作
bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

#include "Heap.h"

/*-------------------------打印堆内容（辅助函数）-------------------------*/
void PrintHeap(HP* php) 
{
    printf("堆内容(大小=%d, 容量=%d): ", php->size, php->capacity);
    for (int i = 0; i < php->size; i++) 
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");
}

void TestHeap() 
{
    HP hp;
    HPInit(&hp);

    printf("===== 开始堆(Heap)测试 =====\n");

    /*------------------测试堆的插入和向上调整------------------*/
    printf("\n------测试插入和向上调整------\n");
    HPPush(&hp, 5);
    HPPush(&hp, 3);
    HPPush(&hp, 8);
    HPPush(&hp, 1);
    HPPush(&hp, 2);
    PrintHeap(&hp);

    printf("堆顶元素: %d (应为1)\n", HPTop(&hp));
    printf("当前堆大小: %d (应为5)\n", hp.size);

    /*------------------测试堆的删除和向下调整------------------*/
    printf("\n------测试删除和向下调整------\n");
    HPPop(&hp);
    PrintHeap(&hp);
    printf("删除堆顶后新堆顶: %d (应为2)\n", HPTop(&hp));

    HPPop(&hp);
    PrintHeap(&hp);
    printf("再次删除堆顶后新堆顶: %d (应为3)\n", HPTop(&hp));

    /*------------------测试堆的判空------------------*/
    printf("\n------测试堆判空------\n");
    printf("当前堆是否为空: %s (应为否)\n", HPEmpty(&hp) ? "是" : "否");

    /*------------------测试边界情况------------------*/
    printf("\n------测试边界情况------\n");
    while (!HPEmpty(&hp)) 
    {
        HPPop(&hp);
    }
    PrintHeap(&hp);
    printf("清空堆后大小: %d (应为0)\n", hp.size);
    printf("清空堆后是否为空: %s (应为是)\n", HPEmpty(&hp) ? "是" : "否");

    /*------------------清理堆------------------*/
    HPDestroy(&hp);
    printf("\n堆已销毁\n");
    printf("\n===== 堆测试完成 =====\n");
}

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

---------------------------------Heap.h---------------------------------
    
#pragma once
#include <stdio.h>


typedef int HPSortType;

//任务1：声明堆的常用的工具函数
//1.交换数组中两个元素
//2.堆的向上调整算法（用于插入元素后维护堆的性质）
//3.堆的向下调整算法（用于删除元素后维护堆的性质）

void Swap(HPSortType* a, HPSortType* b);
void AdjustUp(HPSortType* a, int child);
void AdjustDown(HPSortType* a, int parent, int n);

//注意：这里我们使用的这些工具函数的形参不是：堆，；而是：动态数组
//原因：传参时传入动态数组是因为这些工具函数不仅可以用在实现“堆”这种的数据结构上，还可以继续使用在“堆排序”上


//任务2：实现：“堆排序”函数
void Heapsort(HPSortType* arr, int n);   

---------------------------------HeapSort.c---------------------------------

#include "Heap.h"

//1.实现：“交换两个元素的值”工具函数
void Swap(HPSortType* a, HPSortType* b)//形参是是指针类型，函数中的修改会影响到原数组中的值
{
	HPSortType tmp = *a;
	*a = *b;
	*b = tmp;
}


//2.实现：“向上调整算法”工具函数
void AdjustUp(HPSortType* a, int child)
{
	//1.计算出父节点在数组中的下标（我们有孩子 ---> 得到双亲）
	int parent = child - 1 >> 1;

	//2.接下来不断的进行向上调整，何时调整结束？ ---> 回答：1.当孩子已经调整成根节点时 2.当孩子不满小堆的性质时（这里我们模拟小根堆）
	while (child > 0)
	{
		//3.使用if-else语句进行小根堆的条件检查（小根堆：谁小谁当爹）
		if (a[child] >= a[parent]) return;
		else
		{
			//4.1：交换的孩子节点和双亲节点的值
			Swap(&a[child], &a[parent]);
			//4.2：更新孩子的索引 ---> 因为我们要为孩子找到一个合适的位置
			child = parent;
			//4.3：求出现在孩子的双亲节点的索引
			parent = child - 1 >> 1;
		}
	}
}



//3.实现：“向下调整算法”工具函数
void AdjustDown(HPSortType* a, int parent, int n)
{
	//1.计算出孩子节点在数组中的下标（我们有双亲节点 --->  得到“值最小的”孩子）
	//这里和向上调整有点不一样：找双亲节点就只有一个，但是找孩子节点有两个，要找哪一个呢？---> 找值最小的孩子

	//注：这里使用假设法：假设双亲的左孩子是最小的孩子
	int minchild = (parent << 1) + 1;

	//2.接下来不断地进行向下调整，何时调整结束 --->  1.当孩子节点的索引已经大于数组的容量，即：孩子不存在时 2.当孩子不满足小根堆的条件检查时
	while (minchild < n)
	{
		//3.调整出minchild代表是最小的孩子
		if (minchild + 1 < n && a[minchild + 1] < a[minchild])
		{
			minchild++; //切换到右孩子
		}

		//3.使用if-else语句进行小根堆的条件检查
		if (a[minchild] >= a[parent]) return;
		else
		{
			//4.1：交换孩子节点和双亲节点的值
			Swap(&a[minchild], &a[parent]);
			//4.1：更新双亲节点的索引
			parent = minchild;
			//4.2：求出现在双亲节点的孩子节点的索引
			minchild = (parent << 1) + 1;
		}
	}
}

//实现：“堆排序”操作
void Heapsort(HPSortType* arr, int n)
{
	//1.建堆阶段：（在原数组上进行建堆）

	//1）实现：向上调整建堆：时间复杂度O(nlogn)
	/*
	//强调：这里的i是孩子节点的索引
	for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}
	*/

	//2）实现：向下调整建堆：时间复杂度O(n)
	//强调：这里的i是双亲节点的索引
	for (int i = n - 1 - 1 >> 1; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}

	//2.排序阶段：（本质是删除堆的堆顶元素）

	//2.0：存储堆中最后一个元素的索引
	int end = n - 1;
	while (end > 0)
	{
		//2.1：将堆顶元素和末尾元素进行交换
		Swap(&arr[0], &arr[end]);
		//2.2：更新数组的容量 --- 将堆的末尾的元素删除掉
		end--;
		//2.3：重新调整堆
		AdjustDown(arr, 0, end + 1); //注意：这里的第三个参数：是堆中元素的数量
	}
}

--------------------------------Test.c--------------------------------
    
#include "Heap.h"

int main()
{
	//1.定义一个无序数组
	int arr[] = { 15,1516,14,645,3,9,65,63,4,54 };

	//2.调用HeapSort函数进行排序
	Heapsort(arr, sizeof(arr) / sizeof(int));

	//3.打印原来的无序数组
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*****************************************************************
 * @brief 测试TopK算法实现（查找最大的前k个数）
 * @note 算法核心思想：
 * 1. 使用小堆维护当前最大的k个数
 * 2. 堆顶始终是这k个数中的最小值
 * 3. 遇到更大的数时替换堆顶并调整堆
 * 时间复杂度：O(N logK)  空间复杂度：O(K)
 * 适用场景：海量数据中查找极值（内存无法容纳全部数据时）
 *****************************************************************/

 //任务1：实现：“交换两个元素的值”工具函数
void Swap(int* a, int* b)//形参是是指针类型，函数中的修改会影响到原数组中的值
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//任务2：实现：“堆的向下调整的算法”工具函数
void AdjustDown(int* a, int parent, int n)
{
	//1.计算出孩子节点在数组中的下标（我们有双亲节点 --->  得到“值最小的”孩子）
	//这里和向上调整有点不一样：找双亲节点就只有一个，但是找孩子节点有两个，要找哪一个呢？---> 找值最小的孩子

	//注：这里使用假设法：假设双亲的左孩子是最小的孩子
	int minchild = parent << 1 + 1;

	//2.接下来不断地进行向下调整，何时调整结束 --->  1.当孩子节点的索引已经大于数组的容量，即：孩子不存在时 2.当孩子不满足小根堆的条件检查时
	while (minchild < n)
	{
		//3.调整出minchild代表是最小的孩子
		if (minchild + 1 < n && a[minchild] > a[minchild + 1])
		{
			minchild++; //切换到右孩子
		}

		//3.使用if-else语句进行小根堆的条件检查
		if (a[minchild] >= a[parent]) return;
		else
		{
			//4.1：交换孩子节点和双亲节点的值
			Swap(&a[minchild], &a[parent]);
			//4.1：更新双亲节点的索引
			parent = minchild;
			//4.2：求出现在双亲节点的孩子节点的索引
			minchild = parent << 1 + 1;
		}
	}

}

//任务3：生成随机的测试数据文件
void CreateData()
{
	/*--------------------第一阶段：参数设置--------------------*/
	//1.定义数据量的大小
	int n = 1e5;
	//2.定义数据源文件路径
	const char* file = "data.txt";

	/*--------------------第二阶段：初始化随机数发生器--------------------*/
	srand(time(0));

	/*--------------------第三阶段：打开输出文件--------------------*/
	FILE* fin = fopen(file, "w");
	//2.处理打开失败的情况
	if (fin == NULL)
	{
		perror("file fail");
		return;
	}

	/*--------------------第四阶段：生成数据到文件中--------------------*/
	//1.循环生成随机数
	for (int i = 0; i < n; i++)
	{
		/*
		  1. rand()生成伪随机数
		  2. 加入循环变量i避免连续重复
		  3. 取模限制数值范围
		*/
		int x = (rand() + i) % 10000000; //注意：这里10000000不要写成1e7的形式


		//2.将生成的随机数写入到文件中
		fprintf(fin, "%d\n", x);
	}

	/*--------------------第五阶段：资源清理--------------------*/
	fclose(fin); //关闭文件

}



//在main函数中实现topK问题的测试
int main()
{
	CreateData();

	/*--------------------第一阶段：初始化--------------------*/
	//1.定义topK的K
	int k;
	printf("请输入K的值\n");
	scanf("%d", &k);


	//2.动态创建堆数组（模拟容量是K的小根堆）
	//2.1：使用malloc开辟动态空间
	int* kminheap = (int*)malloc(k * sizeof(int));
	//2.2：处理空间开辟失败的情况
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return 0;
	}

	/*--------------------第二阶段：加载数据--------------------*/
	//1.定义数据源文件路径
	const char* file = "data.txt";
	//2.将文件以只读的模式打开
	FILE* fout = fopen(file, "r");
	//3.处理文件打开失败的情况
	if (fout == NULL)
	{
		//3.1：输出错误的信息
		perror("fopen fail");
		//3.2：释放已经分配的内存空间 + 直接进行返回
		free(kminheap);
		return 0;
	}

	//4.加载文件中的前K个数到数组
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}


	/*--------------------第三阶段：堆的构建--------------------*/
	//使用向下调整堆进行堆的构建操作
	for (int i = k - 1 - 1 >> 1; i >= 0; i--)
	{
		AdjustDown(kminheap, i, k);
	}

	/*--------------------第三阶段：topK筛选--------------------*/
	//1.存储从文件中读到的数据
	int x = 0;
	//2.逐行从文件中读取剩余的数据 (直到读到文件结束符)
	while (fscanf(fout, "%d", &x) > 0)
	{
		//3.将大于小根堆堆顶的元素添加到堆中
		if (x > kminheap[0])
		{
			//3.1：替换堆顶元素
			kminheap[0] = x;
			//3.2：调整堆的结构
			AdjustDown(kminheap, 0, k);
		}
	}

	/*--------------------第三阶段：输出结果--------------------*/
	printf("最大的前K个元素是：\n");
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);

	}
	printf("\n");

	/*--------------------第三阶段： 资源释放--------------------*/
	
	free(kminheap); //释放堆内存
	fclose(fout); //关闭文件
	return 0;
}