Hello,大家好 专栏持续更新中，感谢大家关注 有什么问题可以留言！！！！！！！！

专栏地址小李的刷题之路

1 什么是堆

堆是一种特殊的数据结构，它是一棵完全二叉树。把所有的元素按照完全二叉树的结构，按照层序遍历的顺序储存在一维数组中，如果该二叉树满足父节点小于等于子节点，叫做最小堆（小根堆）；如果该二叉树满足父节点大于等于子节点，叫做最大堆（大根堆）。

2 堆的实现

2.1 堆类型的创建

堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。

堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数。

typedef int HPDataType;
 
typedef struct heap
{
 HPDataType *arr;
 int size;
 int capacity;
}Heap;

2.2 堆的初始化

void HeapInit(Heap* hp)
{
 assert(hp);
 hp->arr = NULL;
 hp->size = hp->capacity = 0;
}

2.3 堆向下调整算法

给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的 向下调整算法 可以把它调整成一个 小堆 。向下调整算法有一个前提：左右子树必须是一个堆（包括大堆和小堆） ，才能调整。

从根节点开始，不断往下调。

选出根节点的左右孩子中小的那个孩子，再与父亲进行比较。

(1)如果父亲小于孩子，就不需处理了，整个树已经是小堆了。

(2) 如果父亲大于孩子，就跟父亲交换位置，并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止

【时间复杂度】我们以满二叉树计算，最坏情况下，向下调整算法最多进行满二叉树的高度减 1 次比较，则说明向下调整算法最多调整满二叉树的高度减 1 次，n 个节点的满二叉树高度为 log₂(n+1)，估算后所以时间复杂度为 O(log₂n)。 

2.4 向上调整算法

思路和向下调整算法差不多,

2.5 堆的插入

• 在堆尾插入并保持堆的结构不变
• 对堆尾插入的那个元素进行向上调整

2.6 堆的删除

删除堆顶的数据，同时保持堆的结构不变

如果直接删除堆顶的元素的话，堆的结构就会被破坏，就必须要重新建堆，所以这里采取的方法是：

将堆的最后一个元素和堆顶的元素交换，删除堆最后一个元素（size–），并对整个堆进行一次向下调整

2.7 堆的销毁

void HeapDestrop(Heap* hp)
{
 assert(hp);
 free(hp->arr);
 hp->size = hp->capacity = 0;
}

3 堆的创建

给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但还不是一个堆，现在我们可以通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

为什么要倒着调整呢？

因为这样我们可以把倒数第一个非叶子节点的子树的左右子树看成是一个 (大 / 小) 堆，满足向下调整的前提条件，这时才能去使用向下调整算法。 

int a[] = {1,5,3,8,7,6};

建堆过程演示（以建大堆为例）：从下到上，依次遍历完所有非叶子节点，分别对每个子树进行向下调整。依次进行每一步，方框内的树进行向下调整为一个大堆。

调换 1 和 8 的位置时，8 的其左子树构成的递归结构被破坏。因此，在每一次发生元素交换时，都需要递归调用重新构造堆的结构。

#include <stdio.h>
#include <stdlib.h>
 
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// 向下调整算法 -- 建大堆，把小的节点往下调整
void AdjustDown(int* 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 HeapSort(int* a, int n)
{
	// O(N)
    // botto-top(自底向上)，依次遍历完所有子树，分别对其进行调整
	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;
	}
}

4 堆排序

给我一组数据，如果对他进行堆排序，那么前提就需要把它变成一个堆的形式。

时间复杂度：O(Nlog⁡N)

升序

建大根堆。堆顶一定是最大的，通过不断地将当前最大的元素与末尾元素进行交换，并重新调整剩余元素形成新的堆（调整时不包含交换后最后一个元素），这样依次可以得到次大的，通过循环n - 1次，最终得到一个升序的数组。

void HeapSort2(Heap *hp)
{
    int i = 0, n = hp->size, *a = hp->arr;
    assert(hp);
    assert(a);
 
    //向下调整算法构建小根堆
	for (i = n/2 - 1; i >= 0; i--) {
		AdjustDownLittle(a, n, i);
	}
    
    //排序O(N * logN)
    for (i = n - 1; i > 0; i--) {
        swap(&a[0], &a[n - 1 - i]);
        AdjustDownLittle(a, i, 0);
    }
}

降序

建小根堆。堆顶一定是最小的，通过不断地将当前最小的元素与末尾元素进行交换，并重新调整剩余元素形成新的堆（调整时不包含交换后最后一个元素），这样依次可以得到次小的，通过循环n - 1次，最终得到一个降序的数组。

void HeapSort2(Heap *hp)
{
    int i = 0, n = hp->size, *a = hp->arr;
    assert(hp);
    assert(a);
 
    //向下调整算法构建小根堆
	for (i = n/2 - 1; i >= 0; i--) {
		AdjustDownLittle(a, n, i);
	}
    
    //排序O(N * logN)
    for (i = n - 1; i > 0; i--) {
        swap(&a[0], &a[n - 1 - i]);
        AdjustDownLittle(a, i, 0);
    }
}

5 TOP-K问题

对于求数据中前K个最大的元素或者最小的元素的问题，堆的应用可以有效地解决。通过构建一个最大堆（或最小堆），然后不断地删除堆顶元素，直到找到K个元素为止。这个过程的时间复杂度主要取决于构建堆的时间和删除堆顶元素的时间，通常这些操作的时间复杂度都是O(Nlog⁡N)

6 时间复杂度对比

‌堆的建立‌：堆的建立包括向上调整建堆和向下调整建堆两种操作。向上调整建堆的时间复杂度为O(Nlog⁡N)，而向下调整建堆的时间复杂度为O(N)。这表明向下调整建堆在效率上更高‌。

堆排序‌：堆排序是通过构建堆后，通过一系列的交换操作来实现排序。在构建堆的过程中，主要涉及到的是向下调整建堆的操作，其时间复杂度为O(N)。在排序阶段，通过不断地将当前最大的元素（或最小的元素）与末尾元素进行交换，并重新调整剩余元素形成新的堆，这个过程的时间复杂度也是O(N)。因此，堆排序的总时间复杂度为O(Nlog⁡N)，这是因为构建堆的时间复杂度O(log⁡N)与排序阶段的时间复杂度O(N)相乘得到‌的。

TOP-K问题‌：对于求数据中前K个最大的元素或者最小的元素的问题，堆的应用可以有效地解决。通过构建一个最大堆（或最小堆），然后不断地删除堆顶元素，直到找到K个元素为止。这个过程的时间复杂度主要取决于构建堆的时间和删除堆顶元素的时间，通常这些操作的时间复杂度都是O(Nlog⁡N)。

7 堆的应用场景

‌堆的应用场景主要包括堆排序、构建优先队列、求Top K值问题、求中位数、合并有序文件、流数据中的第K大元素等。