【数据结构】用堆解决Top-K问题

// TopK问题：找出N个数里面最大/最小的前K个问题
// 找最大的前K个，建立K个数的小堆
// 找最小的前K个，建立K个数的大堆
void PrintTopK(int* a, int n, int k)//对大的前K
{
	HP hp;
	HeapInit(&hp);

	for (int i = 0; i < k; i++)//建立一个小堆
	{
		HeapPush(&hp, a[i]);
	}
	for (int i = k; i < n ; i++)
	{
		if (HeapTop(&hp) < a[i])//比较和调整（维护堆，保证始终是最大的前K）
		{
			hp.a[0] = a[i];
			AdjustDown(hp.a, k, 0);
		}
	}
	HeapPrint(&hp);
}

void TestTopk()
{
	int n = 1000000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (size_t i = 0; i < n; ++i)//产生一万个数据
	{
		a[i] = rand() % 1000000;//都比100w小的数
	}
	// 再去设置10个比100w大的数（随机设置）
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[5355] = 1000000 + 3;
	a[51] = 1000000 + 4;
	a[15] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	PrintTopK(a, n, 10);//打印
}

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//默认堆中的数据类型
typedef int HPDataType;
//堆结构体类型
typedef struct Heap
{
	HPDataType* a;//数组指针（指向动态开辟的空间）
	int size;//堆中存放的数据个数
	int capacity;//堆的容量（数组长度）
}HP;
//堆初始化
void HeapInit(HP* hp);
//堆销毁
void HeapDestroy(HP* hp);
//入堆
void HeapPush(HP* hp, HPDataType x);
//出堆
void HeapPop(HP* hp);
//堆数据打印
void HeapPrint(HP* hp);
//堆顶数据
HPDataType HeapTop(HP* hp);
//堆存入数据个数
int HeapSize(HP* hp);
// 堆的判空
bool HeapEmpty(HP* hp);
//交换函数
void Swap(HPDataType* a, HPDataType* b);
//数据调整(实现大堆)
void AdjustUp(HPDataType* a, int child);
//数据调整
void AdjustDown(HPDataType* a, int size, int parent);

//堆初始化
void HeapInit(HP* hp)
{
	assert(hp);//避免传入参数错误
	//初始化
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
//堆销毁
void HeapDestroy(HP* hp)
{
	assert(hp);//避免传入参数错误
	//释放
	free(hp->a);
	hp->capacity=hp->size=0;
}
//数据调整
void AdjustUp(HPDataType* a, int child)//
{
	int parent = (child - 1) / 2;
	while (child)
	{
		if (a[parent] > a[child])//不符合情况交换
			Swap(&a[parent], &a[child]);
		else
			break;

		//调整下标
		child = parent;
		parent = (child - 1) / 2;
	}
}
//数据调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child<size)
	{		
		//找到数据小的儿子
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		
		//将父节点与小子节点交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);//交换数据
			parent = child;//调整下标位置
			child = parent * 2 + 1;
		}
		else
		{
			break;//结束调整
		}
	}
}
//入堆
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);//避免传入参数错误
	//满堆的情况
	if (hp->size == hp->capacity)
	{
		//如果容量为0则开辟4个空间，否则扩展成原来的两倍
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HP* tmp = (HP*)realloc(hp->a, sizeof(HP) * newcapacity);
		if (tmp == NULL)//开辟失败则打印错误并结束进程
		{
			perror("realloc fail:");
			exit(-1);
		}
		hp->capacity = newcapacity;
		hp->a = tmp;
	}
	//入堆操作
	hp->a[hp->size] = x;//入尾端，再调整
	hp->size++;

	//数据调整
	AdjustUp(hp->a, hp->size - 1);//传入数组地址和下标
}
//出堆（删除堆顶的数据）
void HeapPop(HP* hp)
{
	assert(hp);//避免传入参数错误
	assert(hp->size);//空堆的情况
	
	Swap(&hp->a[0], &hp->a[hp->size - 1]);//先将堆顶数据与堆尾交换
	hp->size--;//再将记录数据个数变量减减实现删除的效果

	//对现在堆顶的数据进行下调
	AdjustDown(hp->a, hp->size, 0);
}
//堆数据打印
void HeapPrint(HP* hp)
{
	assert(hp);//避免传入参数错误

	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}printf("\n");
}
//堆存入数据个数
int HeapSize(HP* hp)
{
	assert(hp);//避免传入参数错误

	return hp->size;
}
// 堆的判空
bool HeapEmpty(HP* hp)
{
	assert(hp);//避免传入参数错误

	return hp->size==0;
}
//交换函数
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}