【数据结构】堆(Heap)

一、堆的概念及结构

堆(Heap)是一种特殊的非线性结构。堆中的元素是按完全二叉树的顺序存储方式存储在数组 中。满足任意结点的值都大于等于左右子结点的值，叫做大堆，或者大根堆；反之，则是小堆，或者小根堆。

不熟悉二叉树的小伙伴可以先跳转→二叉树详解←学习。

堆分为小根堆和大根堆。

小根堆：所有父结点都小于等于左右孩子结点。
大根堆：所有父结点都大于等于左右孩子结点。

堆的性质：

1.堆是一棵完全二叉树。
2.堆中某个节点的值总是不大于或不小于其父节点的值。
3.如果一个堆为大（小）根堆，则它的左右子树也都是大（小）根堆。
4.小堆的存储结构不是升序，大堆的存储结构也不是降序。
5.堆中任意结点下标为 i，则它的左孩子结点下标为2i+1，右孩子结点下标为2i+2，父结点下标为(i-1)/2。

二、堆的实现

堆的两个重要算法：向上调整和向下调整。

1.向上调整算法

向上调整一般在堆中插入元素时使用。

具体实现(小根堆示例)：
1.给定一个数组和一个结点下标，该结点与其父结点的值进行比较。
2.如果该结点的值 ≥ 其父结点的值，已经是小堆了，则不再继续调整；
3.如果该结点的值 < 其父结点的值，需要将二者交换，然后将父结点当做孩子结点，继续向上对比和交换，直到调整到堆顶。

如果是小根堆，只需要改变判断符号>改为<即可。

//小根堆 向上调整
void AdjustUp(DataType* a, int child)
{
	int parent = (child - 1) / 2;//父结点下标
	while (a[child] < a[parent])//建大堆
	{
		Swap(&a[child], &a[parent]);
		child = parent;
		parent = (child - 1) / 2;
	}
}
//交换函数
void Swap(DataType* p1, DataType* p2)
{
	DataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

向上调整算法的比较次数最多不超过二叉树的高度，所以时间复杂度为O(logN)

2.向下调整算法

堆的向下调整算法比较常用，堆排序和堆的创建都会用到向下调整算法。

向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

具体实现(小根堆示例)：
1.从该结点开始，与其左右孩子结点中比较大（较小）的结点进行比较。
2.如果该结点的值 ≤ 其较小（较大）孩子结点的值，已经是小堆了，则不再继续调整；
3.如果该结点的值 > 其较小（较大）孩子结点的值，需要将二者交换，然后将较小的孩子结点当做父结点，继续向下对比和交换，直到调整到叶子结点。

//向下调整
void AdjustDown(DataType* a, int parent, int n)
{
	int child = 2 * parent + 1;
	while (child < n)
	{
		//选出较小的孩子
		if (child + 1 < n && a[child + 1] < a[child])//右孩子不能越界访问，注意判断顺序不能反
		{
			child++;
		}
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

同样，向下调整算法的比较次数最多也不会超过二叉树的高度，所以时间复杂度为O(logN)

3.堆的创建

给定一个数组，怎么创建成一个堆呢？ 根结点的左右子树都不是堆，该怎么调整？

向上调整建堆：

从根结点开始调整

从根结点的左孩子结点开始（因为根结点本身可以看做一个堆），每个结点都向上调整，此时该结点前面的所有结点都已经构成了一个堆，直到调整到最后一个结点，就可以调整成堆。

// 向上调整建堆 效率O(N*logN)
for (int i = 1; i < n; i++)
{
    AdjustUp(a, i);
}

向上调整建堆的时间复杂度是多少？

每个结点最多需要向上调整的次数与层数有关，若层数为k，则最多最多向上调整logk次。而随着层数越大，每层的结点数也越多。假设二叉树的高度为h，则向上调整为堆最多需要调整的次数为0×2⁰+1×2¹+2×2²+3×2³+…+(h-1)×2^h-1
= (h-2)×2^h（错位相减，高中知识，具体过程略），又因为树的高度h=log(n+1)，所以时间复杂度的量级为O(N*logN)。

向下调整建堆：

从最后一个非叶子结点开始倒着调整

因为向下调整建堆需要满足左右子树都是堆的前提，所以我们可以从最后一个结点开始依次向下调整，因为最后一个结点本身可以看做是一个堆。但是因为叶子结点向下调整并不会发生变化，所以我们可以优化代码，从最后一个叶子结点的父结点也就是最后一个非叶子结点开始调整。

//向下调整建堆 效率O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
    AdjustDown(a, i, n);
}

向下调整建堆的时间复杂度是多少？

因为向下调整建堆是从最后一个非叶子结点开始倒着调整的，随着层数的减小，每层的结点数也越少，但是结点向下调整的次数在增加，具体推导过程这里不过多介绍，最后的时间复杂度的量级是O(N)。

综上所述，向上调整建堆的时间复杂度为O(N*logN)，向下调整建堆的时间复杂度为O(N)，所以使用向下调整建堆的效率更高效。实际应用中，一般都使用向下调整算法建堆。

堆的定义、初始化、销毁
堆是以数组的方式存储的，所以堆的定义、初始化、销毁和顺序表一样。

#define INIT_SZ 10//初始空间大小
#define INC_SZ 4	//每次扩容的数量
typedef int HDataType;
typedef struct Heap
{
	HDataType* a;
	int size;
	int capacity;
}Heap;

//初始化
void HeapInit(Heap* php)
{
	assert(php);
	php->a = (HDataType*)malloc(sizeof(HDataType) * INIT_SZ);
	if (NULL == php->a)
	{
		perror("malloc");
		return;
	}
	php->size = 0;
	php->capacity = INIT_SZ;
}

//销毁
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

4.堆的插入

堆的插入需要用到向上调整算法。

实现步骤：
1.在堆的末尾插入一个元素；
2.该元素向上调整，直到满足堆的性质。

//入堆
void HeapPush(Heap* php, HDataType x)
{
	assert(php);
	//扩容
	if (php->size == php->capacity)
	{
		HDataType* tmp = (HDataType*)realloc(php->a, sizeof(HDataType) * (INC_SZ + php->capacity));
		if (NULL == tmp)
		{
			perror("malloc");
			return;
		}
		php->a = tmp;
		php->capacity += INC_SZ;
	}
	php->a[php->size++] = x;//尾插
	AdjustUp(php->a, php->size - 1);//向上调整
}

5.堆的删除

删除的是堆顶的元素，删除之后仍然保证是堆
堆的删除需要用到向下调整算法。

实现步骤：
1.将堆顶元素与最后一个元素交换；
2.堆长度-1，即删除最后一个位置；
3.将交换后的堆顶元素向下调整。

void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	//将尾数据和堆顶数据交换，交换后的堆顶元素再向下调整
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;//堆的有效长度-1
	AdjustDown(php->a, 0, php->size);
}

6.堆的其他操作

//返回堆顶元素
HDataType HeapTop(Heap* php)
{
	assert(php);
	return php->a[0];
}
//判堆空
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}
//堆的元素个数
int HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}

三、堆的应用

1.堆排序

从前面的学习我们知道，堆结构的层序遍历，也就是从上到下每一层的从左到右，并非是有序的，也就是说堆存储在数组中的数据并不是有序的。比如下面这个大根堆，在数组中就是10,5,9,4,3,1,7 我们如何利用堆的特性将这些数据排序呢？

我们知道，大根堆的堆顶一定是最大的，小根堆的堆顶一定是最小的，所以利用这一个特点，我们可以取出堆顶元素，然后将剩下的元素重新调整成堆，再取堆顶元素，再调整剩下的元素，依次类推直到最后一个元素，就可以实现堆排序了。

但是，如果我们将堆顶元素按兵不动，将剩下的元素原地调整成堆，但剩下的元素会被完全打乱，完全不符合堆的性质，需要重新建堆，最后虽然也可以排序，但是效率却很低。这样的话跟普通排序没什么区别，每次找最大值（最小值）就好了，并没有用到堆的优势。

堆排序的实现步骤：
1.先将数组建堆；
2.将堆顶元素与堆末尾元素交换；
3.堆有效长度-1；
4.再将堆顶元素向下调整，直到调整到成堆

这不就是先建一个堆，再进行堆的删除操作吗？没毛病，原理是一样的。

比如一个大根堆，我们取出堆顶元素（最大数）与最后一个数交换，交换后的最大数不看作在堆里面，那么堆顶元素的左右子树仍满足堆的性质，堆的结构并没有被破坏，然后堆顶元素向下调整成堆，即可选出第二大的数，以此类推到最后一个元素，就可以成功实现堆排序了。

堆排序就是每次将堆顶元素从数组的末尾往前放，所以排升序建大堆，排降序建小堆

//堆排序
void HeapSort(int* a, int n)
{
    //建堆：排升序建大堆，排降序建小堆
    //倒着调整，从最后一个非叶子结点开始向下调整建堆 效率O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, i, n);
    }

    //O(N*logN)
    int end = n - 1;//堆的有效长度
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, 0, end);
        end--;
    }
}

堆排序的时间复杂度是O(N*logN)

2.Top-K问题

Top-K问题：求集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：游戏中排行榜前50名，全校前10名等。

对于Top-K问题，自然第一个想到的就是排序，没毛病。但是数据量很大的情况下，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。

第二种方法就是用堆来解决。

实现方法：

1. 用数据集合中前K个元素来建堆。
    前k个最大的元素，则建小堆
    前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。比较完后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

如果选前k个最大值，需要建小堆。
原理分析：小堆的堆顶元素是这k个数据中最小的元素，如果剩下N-K个元素中有大于堆中最小值的，说明这个数可以进入前k名；如果剩下N-K个元素中有小于堆中最小值的，则无法进入前k名。但是如果建大堆的话，堆顶元素就无法作为标准了。

void TopK(int* a, int n, int k)
{
    //用a中前k个元素建堆
    for (int i = (k - 2) / 2; i >= 0; i--)
        AdjustDown(a, i, k);
    for (int i = k; i < n; i++)
    {
        if (a[i] < a[0])
        {
            Swap(&a[i], &a[0]);//不满足则交换
            AdjustDown(a, 0, k);//向下调整
        }
    }
    for (int i = 0; i < k; i++)
        printf("%d ", a[i]);
}

上述代码只是选出前k个最大值或最小值，并没有将这k个数排序，如果要实现排序功能自行添加即可。

堆的完整代码放在gitee：https://gitee.com/ncu-ball/study/tree/master/24_4_19