【C】堆的实现及应用（Tok问题、排序）

文章介绍了堆的基本定义以及代码实现，并针对常用的TopK问题、排序方法做了应用模拟，同时对有可能出现的疑问做了解释说明，希望可以帮助到大家，如有错误，还望不吝赐教。

一、基本知识

在百度百科中，基本定义如下： 简陋一些讲，就是一棵完全二叉树，其中任意节点的值都大于（小于）它的孩子节点，称为大根（小根）堆； 由于完全二叉树常采用顺序结构存储，故堆也通常采用顺序结构的数组实现。

二、堆的实现（以小堆为例）

a.结构体实现

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
// 初始化
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

b.堆的调整

向下调整算法

插入数据后，依次与孩子比较，慢慢“沉底”。 运行步骤：1、确定调整的位置；2、比较其孩子大小；3、若存在孩子比它小，则将最小的孩子与它交换；若不存在，则退出调整，表明此时已调整完成；4、继续调整：从交换后的位置继续2、3步骤。 前提：左右子树必须是小堆；why：若其左右子树存在不为小堆的情况，则交换后，上一层有可能不满足小堆条件，从而导致调整失效，如下例： 用途：常用于堆顶插入数据时，对堆的调整。 代码如下：

void AdjustDown(HPDataType* a, int n, int parent)
{
	// 初值给左孩子
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 右孩子更小，child指向右孩子
		if (child + 1 < n && 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 AdjustUp(HPDataType* a, int child)
{
	assert(a);
	// 找父亲
	int parent = (child - 1) / 2;
	// child大于0，表示还有父节点未参与比较
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			// 子结点比父节点小，交换值，继续走
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		// 父节点>子结点，根据小根堆定义，往上的结点都大于此结点，于是退出循环
		else
		{
			break;
		}
	}
}

c.堆的基本操作

插入数据

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	// 空间不足，调整空间
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}
	// 尾部插入数据
	php->a[php->size++] = x;
	// 向上调整
	AdjustUp(php->a, php->size - 1);
}
// 以数组a中数据建堆
void HeapInitArray(HP* php, int* a, int n)
{
	assert(php);
	assert(a);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	php->size = n;
	php->capacity = n;

	memcpy(php->a, a, sizeof(HPDataType) * n);
	// 建堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(php->a, i);
	}
}

删除数据

从堆顶删除最小的数；

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	// 将堆顶数据放置到最后
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

其余基本操作

// 打印堆
void HeapPrint(HP* php)
{
	assert(php);

	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
// 销毁堆
void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}
// 堆顶数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}
// 堆判空
bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

三、堆的应用

1、TopK问题求解

存在大量数据时，需要求前k个最大或最小的数据，当数据量太大时，排序有可能会出错（数据量太大以至于不能直接加载入内存中），此时可以应用堆来解决。

步骤：

1、取前k个数据建堆； 2、依次读取随后数据，将满足要求的进堆； 3、读取完所有数据，堆中即为前k个所需的数据。

问题：当需要前k个最大的数据时，建小堆还是大堆？

建小堆。小堆建立后，堆顶即为堆中最小的数据，此时若有数据比它大，入堆即可，依次替换便可保证堆中的数据慢慢刷新为前k个最大的数； 而若建大堆，堆顶数据为堆中最大的数据，此时新数据与堆顶数据比较不能得到新数据是否满足要求，因为不能确定它是否大于堆中所有的数据。 代码如下：

 // 模拟数据
void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));

	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		exit(-1);
	}
	for (size_t i = 0; i < n; i++)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

// 实现代码
void PrintTopK(const char* filename, int k)
{
	// 建堆
	FILE* fout = fopen(filename, "r");
	if (fout == NULL)
	{
		printf("fopen failed");
		exit(-1);
	}
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		printf("malloc failed");
		exit(-1);
	}
	// 将前k个数输入到堆中
	for (size_t i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	// 调整为小堆,完全二叉树中若有n个节点，则其最后一个节点的序号为(k-2)/2，
	for (int i = (k - 2) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}

	// 将剩下的元素依次与堆顶元素比较，大则入堆
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minheap[0])
		{
			// 入堆
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}
	for (size_t i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	free(minheap);
	fclose(fout);
}

2、堆排序

实现步骤，将原有数据调整为堆之后，依次将堆顶数据至于末尾，再依次调整。

建堆时，为何从(n-2)/2处开始调整?

最后一个分支节点，要么子树为空，要么子树只有一个节点，所以满足堆的要求，因此i从最后一个分支节点开始往前调整。令最后一个分支节点的下标为i，两种情况求解分别如下： 总共n个节点

• 只有左子树 左子树下标为$2i+1$,所以有$2i+1+1 = n$,故$i = (n-2)/2$，由完全二叉树性质可得，只有左子树时，节点总数n为偶数。
• 左右子树都有 右子树下标为$2i+2$,有$2i+2+1 = n$,故$i=(n-3)/2$,又由完全二叉树性质可得，此时节点总数n为奇数，所以$(n-3)/2 = (n-2)/2$。

由上，从$i=(n-2)/2$时开始调整。

代码如下：

void Heapsort(int* a, int n)
{
	// 降序，考虑建小堆，然后依次执行类似pop操作，将堆顶置于数组尾部
	// 将原有数据调整为堆，向下调整建堆
	for (int i = (n - 2) / 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--;
	}
}