void AdjustDown(int* a,int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])  //child + 1 < n && a[child + 1] > a[child]大根堆
		{
			++child;
		}
		if (a[child] < a[parent]) //a[child] > a[parent]大根堆
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

交换函数

void Swap(HpDataType* p1, HpDataType* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

对于child的下标上面已经给出了计算公式

图解实例：

小伙伴们可以对照着代码自己画张图进行理解。只有自己把图画出来才能更好的理解代码。

好了，正式开始我们对堆的实现吧

3.2.2 堆的创建

堆的结构

typedef int HpDataType;
typedef struct Heap
{
	HpDataType* a;    //数组
	int size;    //数据个数
	int capacity;    //容量空间
}HP;

初始化堆

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

堆的销毁

void HeapDestroy(HP* php)
{
	assert(php);

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

堆的插入

在进行堆的插入的时候，我们以小根堆为例，大根堆也是类似。插入的时候看需不需要扩容，需要的话，扩容方法跟链表一样。另外我们还要学习一个新算法，叫向上调整算法。先看代码吧

算法思路：1.先将元素插入到堆的末尾，即最后一个孩子之后(可以看成插入到数组的末尾）

2.插入之后如果堆的性质遭到破坏，将新插入节点顺着其双亲往上调整到合适位置即可。

从根开始下标是0

void HeapPush(HP* php, HpDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HpDataType* tmp = (HpDataType*)realloc(php->a, newCapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

void AdjustUp(HpDataType* a,int child)//小根堆
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])  //a[child] > a[parent]大根堆
		{
			Swap(&a[child], &a[parent]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆的删除

堆的删除就要用到向下调整算法了

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

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

HpDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

bool HeapEmpty(HP* php)
{
	assert(php);
	
	return php->size == 0;
}

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

#pragma once
#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 AdjustUp(HpDataType* a, int child);
//向下调整
void AdjustDown(int* a,int n,int parent);

void HeapInit(HP* php);
void HeapDestroy(HP* php);
//插入数据
void HeapPush(HP* php, HpDataType x);
//删除数据
void HeapPop(HP* php);
HpDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

3.3 堆的应用

3.3.1 堆排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

不过向上调整和向下调整都可以，向上调整比向下调整容易理解。这里我会把2个方法都将一下，小伙伴们觉得哪个简单就学习哪个吧。

我们以降序为例，前面我们已经了解到降序需要建小堆，那么向上调整算法（从根开始）该怎么操作才能让无序数组变成一个降序的呢？

我们可以根据代码来看一看。其实这个代码很好理解，小伙伴们可以自己画图来试一试。这里我就不过多演示了。

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;
	}
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	return 0;
}

向下调整建堆

void HeapSort(int* a, int n)
{
	//升序--建大堆
	//降序--建小堆

	//倒着调整--从叶子节点开始调整  O(N)
    //n-1是最后一个数据的下标
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	//O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);

		--end;
	}
}
int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));
	return 0;
}

倒着调整，叶子节点不需要处理，因为叶子节点可以看成大堆或者小堆，从最后一个节点的父亲开始调整。

n是最后一个节点的下一个位置，知道孩子下标找父亲，用公式就可以了parent=(child-1)/2.

3.3.2 TopK问题

TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。

对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前 K 个元素来建堆

        前K个最大的元素，建小堆；前K个最小堆元素，建大堆

2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余 N-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");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 100000;//保证每个数据都在10万以内
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

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

	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc error");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	// 建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}

	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}

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

int main()
{
	CreateNDate();
	PrintTopK(5);

	return 0;
}

代码运行完成之后我们该怎样知道这5个数是不是最大的前5个呢？我们运行的时候可以先把PrintTopK(5)先注释掉，运行代码然后打开文件随便改5个数据保存之后，回到代码窗口，把CreateNDate()注释掉，运行PrintTopK(5)函数，这样就知道是不是前5个最大的了。如果不把随机函数注释掉，那么每次运行就会重新产生随机数。

3.4 建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果）：

向下建堆复杂度：O(N)

向上建堆复杂度O(N*longN)

从时间复杂度上看，向下建堆比向上建堆的时间快，不过向上建堆好理解。所以建议小伙伴们最好2个都能理解。

所以建堆的时间复杂度是N*longN + N = N*longN

4.结语

好了，小伙伴们，今天我们就先学到这里，下一节我们学习二叉树的链式结构的实现，今天的知识点一定要好好理解，该画图的时候画图，不要嫌麻烦，要为后面的学习打基础。