目录

• • 传统艺能😎
  • 堆的概念与结构🤔
  • 堆的实现🤔
  • 向上（向下）调整算法🤔
  • 调整算法的时间复杂度对比🤔
  • 建堆时间复杂度🤔
  • 堆排序🤔
  • Topk问题🤔

传统艺能😎

小编是双非本科大一菜鸟不赘述，欢迎大佬指点江山（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】
乔乔的gitee代码库（打灰人 ）欢迎访问，点我！

🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们，打码路上一路向北，背后烟火，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达： 社区链接点我

堆的概念与结构🤔

前面讲了二叉树的相关概念，堆就是把他的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中。堆可以用来解决堆排序，topk 问题，以后还会涉及到优先级队列。

堆又分为大堆和小堆，我们把根节点最大的堆叫做大（根）堆，即树中父节点 ≥ 子节点，根节点最小的堆叫做小（根）堆，父节点 ≤ 子节点。

堆的性质：

1. 堆中的某个节点的值总是不大于或者不小于其父节点的值；
2. 堆总是一棵完全二叉树；

堆的实现🤔

一般这种实现我们就直接考虑动态版本：

底层结构我们采用的是顺序表的结构，但注意仅仅只是借鉴他的结构，逻辑上他并不是线性表，不应支持头插尾插头删尾删等操作，是不是有了疑问：他的存储结构不就是一个数组吗，为毛不支持啊？原因很简单，要是支持这些操作不就是一个顺序表了嘛，那我干嘛叫堆是吧。

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

向上（向下）调整算法🤔

这里就有一个细节，格局在此提高，我们所谓入堆出堆，都应该时刻维持他作为堆的结构，想象一下我插入一个数后，结果是他有可能是堆有可能不是堆，因为对于父节点的相对大小我并不知道，所以我们实际上插入删除有两步：

1. 插入需要的数据；
2. 对插入后的数据进行调整；

比如给出一个情景：

这里插入的 4 就很明显的破坏了堆的结构，我们小堆必须保证父节点 ≤ 子节点，那我就要做出调整，我们能用下标表示父节点与子节点的数学关系，让他和父节点进行比较再交换，换完观察现阶段结构是否满足，不满足继续换，我们把这种方法称之为：向上调整算法

向上调整算法适用于堆的数据的插入
向下调整算法适用于建队和堆的数据的删除
排升序应建大根堆，排降序应建小根堆

堆的删除是删除堆顶的最大或最大值删除后，但依然需要每次调整堆的数据来满足结构，注意这么一个细节，我们删除是在堆顶删除！

栈顶删除后面子节点就会变成父节点，直接破坏了所有父子间关系，所以采用一般的挪动覆盖是不行的，其实我们根本不用抹去这个数，我们只需要把堆顶和堆尾元素交换，删除最后一个数据，然后再向下调整就行了。

首先为了方便，我们单独把交换功能写成一个函数接口;

void Swap(HPDataType* x1, HPDataType* x2)
{
	int tem;
	tem = x1;
	x1 = x2;
	x2 = tem;
}

实现如下：

void AdjustDown(HPDataType* a, int n, int root)
{
	assert(a);
	int parent = root;
	int child = (parent/2)-1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			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;
	while (child > 0)//不能用parent>=0判断，因为parent始终不小于0
	{
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
	
}

到这里了咱光说不练假把式是吧，看看堆插入怎么搞：

void HeapPush(Heap* hp, HPDataType x)
{
	int i;
	assert(hp);
	if (hp->size == hp->capacity)
	{
		hp->capacity *= 2;
		hp->a = (HPDataType*)realloc(hp->a, sizeof(HPDataType)*hp->capacity);//插入数据

	}
	else
	{
		hp->a[hp->size] = x;
		hp->size++;
		AdjustUp(hp->a,hp->size-1);//调整堆数据
	}
}

那么出堆也是同理：

void HeapPop(Heap* hp)
{
	assert(hp);
	Swap(hp->a[hp->size-1], hp->a[0]);
	hp->size--;
	AdjustDown(hp->a, hp->size,0);
}

送上全部代码：
Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

Heap.c

# define _CRT_SECURE_NO_WARNINGS 
#include"heap.h"
void Swap(HPDataType* x1, HPDataType* x2)
{
	int tem;
	tem = x1;
	x1 = x2;
	x2 = tem;
}

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

void AdjustUp(HPDataType* a, int n, int child)
{
	assert(a);
	int parent = (child- 1)/2;
	while (parent>=0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
	
}

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp&& a);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	hp->size = n;
	hp->capacity = n;
	return hp;
	for (int i = 0; i < n; i++)
	{
		hp->a[i] = a[i];
	}
	for (int i = (n - 2) / 2; i >=0 ; i-- )
	{
		AdjustDown(hp->a,hp->size,i);
	}
}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void HeapPush(Heap* hp, HPDataType x)
{
	int i;
	assert(hp);
	if (hp->size == hp->capacity)
	{
		hp->capacity *= 2;
		hp->a = (HPDataType*)realloc(hp->a, sizeof(HPDataType)*hp->capacity);

	}
	else
	{
		hp->a[hp->size] = x;
		hp->size++;
		AdjustUp(hp->a,hp->size,hp->size-1);
	}
}
	
void HeapPop(Heap* hp)
{
	assert(hp);
	Swap(hp->a[hp->size-1], hp->a[0]);
	hp->size--;
	AdjustDown(hp->a, hp->size,0);
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}

int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

int HeapEmpty(Heap* hp)
{
	return hp->size == 0;
}

void HeapPrint(Heap* hp)
{
	assert(hp);
	int i;
	for (i = 0; i < hp->size; i++)
	{
		printf("%s ", hp->a[i]);
	}
}

调整算法的时间复杂度对比🤔

其实堆的插入与堆的删除时间复杂度都是一样的：logN，其实就是向上调整算法和向下调整算法的时间复杂度，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log2(N+1)（N为树的总结点数），类比为二分搜索就很好理解，因此他和 qsort 是一个量级的。

建堆时间复杂度🤔

堆的本质是一棵完全二叉树，满二叉树是特殊的完全二叉树，我们就直接借满二叉树来计算就行了，建堆包含了调整算法，所以又分为向上调整建堆和向下调整建堆，这里就以向下调整建堆为例：

所以向下调整建堆时间复杂度就是：O(N)

同理，以错位相减法为运算基础，可得向上调整建堆时间复杂为：O(log N)

所以其实两种建堆是有差别的，但差别并不大。

堆排序🤔

堆排序是堆的一种实际运用，是利用堆对数据进行排序的操作，以大堆为例子（已建堆）：
使用向下调整建堆要求左右子树都为堆，但要是不为堆呢？我们就要从倒数第一个非叶子节点开始向下调整，因为叶子节点既可以看成大堆也可以看成小堆，不需要向下调。

void Heapsort(int* a, int n)
{
	assert(a);
	//for(int i =1;i<n;i++)
	//{
	//AdjustUp(a, n, i);//使用向上调整建堆
	//}
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);//使用向下调整建堆倒着调整
	int tail = n - 1;
	while(tail>0)
	{
		Swap(&a[0], &a[tail]);//前后交换
		AdjustDown(a, n, 0);//重新调整堆的结构
		tail--;
	}
}

堆排序的时间复杂度为O(N*log N)

Topk问题🤔

Topk问题指的是找出堆中数据最大的 k 个或者最小的 k 个，比如守望先锋国服前十的仓鼠，CSDN 粉丝数前五的用户等等。找出 topk 元素的方法很简单就是用原数组建立一个大小为 k 的堆，再拿堆顶元素与k之后的元素比较，根据需求进行筛查，不符合就从堆中 pop 掉再插入对应的数组元素，到最后留下来的就是要找的 k 个元素。

//1. 找最大的K个元素
//假设堆为小堆
void SmallTopK(int* a, int n, int k)
{
	Heap hp;
	HeapCreate(&hp, a, n);
	int i;
	for (i = k; i < n; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}	//筛查，不符合条件的替换掉
	}
	for (i = 0; i <k; i++)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
}

//2. 找最小的K个元素
//假设堆为大堆
void BigTopK(int* a, int n, int k)
{
	Heap hp;
	HeapCreate(&hp, a, n);
	int i;
	for (i = k; i < n; i++)
	{
		if (a[i] < HeapTop(&hp))
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
		for (i = 0; i < k; i++)
		{
			printf("%d ", HeapTop(&hp));
			HeapPop(&hp);
		}
	}
}

今天就到这里吧，摸了家人们。