写在前面

---

• 博客主页：kikoking的江湖背景
• 欢迎关注点赞收藏⭐️留言
• 本文由 kikokingzz 原创，CSDN首发！
• 首发时间：2021年12月16日
• 最新更新时间：2021年12月16日
• ✉️坚持和努力一定能换来诗与远方！
• 作者水平很有限，如果发现错误，请留言轰炸哦！万分感谢感谢感谢！

---

• 热榜文章（没错，以下文章全进了热榜）
• 第一话·彻底搞清数据结构中的·逻辑结构&存储结构
• 第二话·彻底搞懂数据结构之·算法复杂度
• 第三话·408必看顺序表之·人生不是“顺序表”
• 第四话·数据结构必看之·单链表就这？
• 第五话·数据结构必看之·栈 真的这么简单？
• 第六话·数据结构必看之·队列 居然这么简单？

目录

 写在前面

1.堆的概念

1.1堆的定义

1.2大根堆与小根堆

例题1

2.堆的逻辑结构

2.1 完全二叉树

2.2 完全二叉树的性质

性质1.已知结点个数求完全二叉树高度

性质2.已知结点总个数求各度结点个数

3.堆的物理结构

3.1顺序存储

4.堆的实现

4.1 堆向下调整算法

向下调整的时间复杂度：O(logN)

算法实现

4.2 建堆

建堆的时间复杂度：O(N)

5.堆排序

5.1 建小堆❌

5.2 建大堆✅

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

5.3 建大堆的逐步操作✅

6.用数组实现堆的一些其他操作

6.1 堆的向下调整操作

6.2 堆的定义

6.3 初始化

6.4 销毁

6.5 堆的插入

6.6 堆顶元素的删除

6.7 取堆顶的数据

6.8 堆的数据个数

6.9 堆的判空操作

6.10 堆的打印

剑指 Offer 40. 最小的k个数

✅思路一

✅思路二

✅思路三：TopK

海量数据处理问题

⭕️解决办法

1.堆的概念

---

1.1堆的定义

·堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值

• 堆总是一棵完全二叉树

---

1.2大根堆与小根堆

·小根堆：父亲<=孩子

·大根堆：父亲>=孩子

---

例题1

✨✨✨我是分割线✨✨✨

2.堆的逻辑结构

---

2.1 完全二叉树

·堆的逻辑结构是一棵完全二叉树

---

2.2 完全二叉树的性质

性质1.已知结点个数求完全二叉树高度

✅证明方法1

✅证明方法2

性质2.已知结点总个数求各度结点个数

✨✨✨我是分割线✨✨✨

3.堆的物理结构

---

3.1顺序存储

堆的物理结构采用顺序存储的存储方式

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左向右存储完全二叉树上的结点元素，即将完全二叉树上编号为A、B、C、D····的结点元素存储在一维数组下标为[0]、[1]、[2]、[3]····的分量中

✨✨✨我是分割线✨✨✨

4.堆的实现

---

4.1 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

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

上述例题中满足：满足左子树和右子树都是小堆，采用向下调整算法：

step1.选出左右孩子中小的那一个（上图中是15）

step2.拿小的这个孩子跟父亲比较

（a）如果小的孩子比父亲小，就跟父亲交换，并且把原来孩子的位置当成父亲，继续向下调整（重复步骤1、2），直到p走到叶子结点。

（b）如果小的孩子比父亲大，则不需要处理，此时整个树已经是小堆

向下调整的时间复杂度：O(logN)

向下调整的次数就是完全二叉树的深度，对于n个结点的完全二叉树，其深度为log2（N）+1向下取整，因此时间复杂度取O(logN）

---

算法实现

可见如上图所示，算法成功实现

//向下调整

void AdjustDown(int* a, int n, int parent)
{
    //parent接收0<------>访问数组a[0]
	int child = parent * 2 + 1;
	while (child < n)
	{
		//选出左右孩子中小的那个
		if ( child + 1< n && a[child + 1] < a[child])
		//前提右孩子存在才进行比较，否则数组越界了
		//如果右孩子小于左孩子
		{
			++child;//选择右孩子
		}
		//否则默认选择左孩子
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

int main()
{
	int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	int n = sizeof(a) / sizeof(a[0]);
	AdjustDown(a, n, 0);//从位置0开始调整
    
    return 0;
}

---

4.2 建堆

当左右子树不是小堆时，怎么办？

✅思路：从底向上进行建堆，在每个子堆中进行向下调整

1.找到最后一个结点对应的父结点（上图中即找到27元素的父结点为65）

2.从结点65开始向下调整，调整完了以后，数组下标i--为a[3]，即接下来从结点34开始向下调整

3.结点34向下调整完毕后，数组i--为a[2]，即从结点18开始向下调整

4.一直i--到a[0]为止，此时所有的元素都向下调整完毕，建堆完成✅

//建堆

	//n-1是最后一个结点的下标
	//(n-1)-1是为了计算父节点下标
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)//从最后一个结点对应的父节点开始向根结点操作
	{
		AdjustDown(a, n, i);//从第i个位置，从底向上调整
	}
	return 0;

建堆的时间复杂度：O(N)

证明如下：

·可见，当N不断增大，log(N+1)可以忽略不计，即时间复杂度为O(N)

✨✨✨我是分割线✨✨✨

5.堆排序

---

5.1 建小堆❌

Q：升序为什么不能建小堆呢？

·建小堆的问题在于：选出最小的数放到第一个位置，紧接着需要选出次小的，如何选？此时如果让18去做根，整棵树的关系都乱了，需要重新建堆，才能选出次小的，建堆时间复杂度为O(N)；如果通过建堆来选数，还不如直接遍历比较选数，堆排序就没有意义了

因为建堆选出最小的数，花了O(N)，紧接再用O(N)选出剩下的（N-1）个数中的次小的数，同时剩下的数父子关系全乱了，只能重新建堆，效率太低

---

5.2 建大堆✅

如上图所示，第一次将最大的数与最后一个数交换；然后不把最后一个数看做堆里面，直接向下调整就能选出次大的（因为父子间的关系没动），

建大堆时间复杂度：O(N)

排序时间复杂度：O(N*logN)

只需要向下调整完全二叉树的高度次，最坏的调整次数是logN次；假设有N个元素，最坏需要调整N*logN次；时间复杂度也就是O(N*logN)

总的时间复杂度：O(N*logN)+O(N) ---> O(N*logN) 

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

·简单分析：堆排序和冒泡排序的差别有多大呢？

假设排100w个数

冒泡排序：N^2 -->  10000亿次

堆排序： N*logN --> 2000万次

---

//排升序-->建大堆
void HeapSort(int* a, int n)
{
	//建堆的时间复杂度是O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);//从第i个位置，从底向上调整
	}
	
	int end = n - 1;
	while (end>0)
	{
		Swap(&a[0], & a[end]);
		AdjustDown(a, end, 0);//n-1个数
		//选出次大的
		--end;
	}

---

5.3 建大堆的逐步操作✅

✨✨✨我是分割线✨✨✨

6.用数组实现堆的一些其他操作

---

6.1 堆的向下调整操作

void AdjustDown(HPDataType* a, int n, int parent)
{
	HPDataType child = parent * 2 + 1;
	while (child < n)
	{
		//选出左右孩子中小的那个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			//前提右孩子存在才进行比较，否则数组越界了
			//如果右孩子小于左孩子
			++child;//选择右孩子
		}
		//否则默认选择左孩子
		if (a[child] > a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

---

6.2 堆的定义

typedef int HPDataType;
struct Heap
{
	HPDataType* a;//a指向数组的首元素地址
	int size;
	int capacity;//扩容需要加入capacity
};

typedef struct Heap HP;//用HP代替struct Heap

---

6.3 初始化

void HeapInit(HP* php, HPDataType* a, int n)//要求以php返回
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);//动态申请一片空间
	if (php->a == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}

	memcpy(php->a, a, sizeof(HPDataType) * n);//将n个数据从a中拷贝到php->a中
	php->size = n;
	php->capacity = n;

	//建堆
	for (int i = (php->size - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(php->a, php->size, i);//在堆php->a中，从第i个元素开始向下调整
	}
}

---

6.4 销毁

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);//释放堆
	php->a = NULL;//将指针php->a置空
	php->size = php->capacity = 0;//将php->size和php->capacity置为0
}

---

6.5 堆的插入

在堆的末尾最后插入一个数，因为不确定最后一个数的大小，因此需要向上调整，如果该结点的父结点比插入的数小，则交换这两个结点；然后用交换后的结点再与新的父结点比较，一直比到最后的父结点为根结点为止；因此我们要写一个向上调整算法：

//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;//找该结点的父结点
	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);//如果父结点小于孩子，就交换
			child = parent;//将父结点的下标赋给孩子
			parent = (child - 1) / 2;
		}
		else
		{
			break;//跳出循环
		}
	} 
}

//堆的插入
void HeapPush(HP* php, HPDataType x)
{
	//满了需要增容
	if (php->size == php->capacity)
	{
		assert(php);
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);//对原来已有的空间扩容到2倍
		if (tmp == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		php->a = tmp;
		php->capacity *= 2;
	}
	php->a[php->size] = x;//在数组的尾部插入x
	php->size++;

	AdjustUp(php->a, php->size - 1);//从size-1的位置向上调整
}

---

6.6 堆顶元素的删除

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);//向下调整
}

---

6.7 取堆顶的数据

HPDataType HeapTop(HP* php)//返回堆堆顶的数据
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];//返回数组中第一个元素的值
}

---

6.8 堆的数据个数

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

---

6.9 堆的判空操作

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

---

6.10 堆的打印

void HeapPrint(HP* php)
{
	for (int i = 0; i < php->size; ++i)
	{
		printf("%d->", php->a[i]);
	}
	printf("n");


	int num = 1;
	int i = 0;
	while (num < php->size)//控制每一层的个数
	{
		for (int j = 0; j < num; ++j) 
		{
			if(isize)//防止数组越界
			printf("%d  ", php->a[i++]);
		}
		printf("n");
		num *= 2;
	}
}

 ✨✨✨我是分割线✨✨✨

剑指 Offer 40. 最小的k个数

---

✅思路一

采用排序，使用最好的排序算法，需要N*logN的时间复杂度

---

✅思路二

采用堆排序（效率更高）

对于含有N个数的数组：

1.把N个数建成小堆  -----> 需要O(N)

2.选一个删一个，不断选出前K个最小 -----> 需要O(logN*k）

因为删除堆头元素的本质是将首尾元素交换，将数组的size-1，然后进行向下调整获得次小的数，向下调整的次数最多为完全二叉树的深度；而选出k个数，就要将此步骤进行k次，因此时间复杂度为O(logN*k)

时间复杂度：O(N)+O(logN*K)

空间复杂度：O(N)

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
    HP hp;
    HeapInit(&hp,arr,arrSize);//建堆，建小堆
    int* retArr=(int*)malloc(sizeof(int)*k);
    for(int i=0;i 
 注意：上述代码中调用了之前写好的堆排序代码 
 

 
✅思路三：TopK 
 
海量数据处理问题 
 
Q:对于含有N个数的数组：假设N是100亿时，k是100
 
 
对于上述这个问题，我们先计算一下存储100亿个整除需要多大的空间
 
 
1 KB=1024 Byte
 
 
1 MB=1024 KB
 
 
1 GB=1024 MB
 
 
1 GB=2^30 Byte=10亿+ Byte
 
 
100亿个整数-->400亿Byte ==40G左右（存在文件中）
 
 
如果此时采用思路二，空间复杂度过大！
 
 
⭕️解决办法 
 
1.先把数组中的前K个数据，建成大堆
 
 
2.然后剩下的N-K个数，跟堆顶的数据比较，如果比堆顶的数据小，则替换堆顶的数据，进堆
 
 
3.最后堆里面就是最小的K个数
 
 
空间复杂度：O(K)
 
 
·建立了一个K个数据的数组（额外空间），因此空间复杂度为O(K)
 
 
时间复杂度：O(N*logK)
 
 
·将N个数进行比较，最坏的情况就是N个数都要进行向下调整，每个数向下调整的最多次数就是这个完全二叉树的深度，因为该数的结点数为K，因此最大深度为logK，因此时间复杂度为N*logK
 
 
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
    if(k==0)
    {
        *returnSize=0;
        return NULL;
    }
    int* arrRet=(int*)malloc(sizeof(int)*k);
    //前k个数建立大堆
    for(int i=0;i=0;--j)//找父节点向下调整
    {
        AdjustDown(arrRet,k,j);
    }
    //剩下的N-k个数
    for(int i=k;i