数据结构--堆和堆排序

前面我们了解了什么是树，以及二叉树
➡️ 树以及二叉树的性质和概念
本文 带你掌握堆和堆排序

文章目录

• 一. 什么是堆？
• • 1. 堆的性质
  • 2. 堆的两种结构
  • 堆的代码结构
  • 堆的初始化
• 二、堆的实现
• • 0. 交换俩数
  • 1. 向下调整算法(以小堆为例）
  • 2.向上调整算法
  • 2. 堆的创建
  • • ① 向上调整建堆
    • ② 向下调整建堆
  • 3. 建堆的时间复杂度分析
  • • ① 向下调整建堆的时间复杂度
    • ② 向上调整建堆的时间复杂度
  • 4. 堆的插入
  • 5. 堆的删除
  • 6. 取堆顶数据
  • 7. 堆的判空
  • 8. 堆元素个数
  • 堆的销毁
• 三、堆的应用.
• • 1. 堆排序
  • • 前言
    • 利用堆排升序（易错！)
  • 2. TOP k问题

一. 什么是堆？

我们前面已经了解什么是二叉树
堆其实就是一种完全二叉树

定义：

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

1. 堆的性质

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

2. 堆的两种结构

堆有两种结构

1. 小根堆
2. 大根堆
   
   
   
   可以看到，堆其实就是二叉树的顺序存储（按数组下标依次存储）
   同时满足每一个父节点的值都要大于等于左右孩子节点的值（大堆）或者小于等于左右孩子节点的值（小堆）

堆的代码结构

typedef int HPDataType;
typedef struct HeapNode {
	HPDataType* a;
	int size;
	int capacity;
}HP;

堆的初始化

//初始化
void HPNodeInit(HP* ph)
{
	assert(ph);
	ph->a = NULL;
	ph->capacity = ph->size = 0;
}

二、堆的实现 0. 交换俩数

因为会频繁用到，所以封装一个函数

//交换两个数
void Swap(HPDataType* a, HPDataType* b)
{
	*a ^= *b;
	*b ^= *a;
	*a ^= *b;
}

1. 向下调整算法(以小堆为例）

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

左右子树必须是堆，如图，左右子树都是一个小堆，这样向下调增的时候，就可以把最小的调整到根节点27的位置！否则如果不是小堆，是无法通过向下调整变成堆的！

int arr[]={27,15,19,18,28,34,65,49,25,37};

结构如图：

调整过程：
（以小堆为例）

1. 找出左右孩子的较小值 min
2. 比较父亲与 min，如果父亲大于min 不满足小堆，交换
3. 之前找的较小的孩子min作为新的父亲 继续迭代向下走
4. 如果下一次迭代中父亲小于等于min，满足小堆，不再继续调整

代码实现

1. parent节点从0开始
2. 由二叉树顺序存储的性质：左孩子下标：2*parent+1,右孩子：2*parent+2
3. 当孩子下标超过数组索引范围 size-1，跳出循环

void AdjustDown(HPDataType* a, int size, int parent)
{
	//默认小孩子是左孩子
	int child = 2 * parent + 1;
	//循环的控制条件是 ：孩子小于size
	while (child < size)
	{
		//child+1 就是右孩子的下标，比较左右孩子哪一个大
		//如果满足右孩子小于左孩子，那么child++（右孩子是小的那个）
		//但是需要注意控制条件：如果没有右孩子，即恰好child==size-1
		//这时候 a[child+1]就越界访问了，就不进入循环了！
		if (child + 1 < size && a[child + 1] < a[child])
		{
			++child;
		}
		//如果不执行上面的if  说明小的那个是左孩子
		//比较child和parent
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//迭代
			parent = child;
			child = 2 * parent + 1;
		}
		else//如果父亲小于孩子 说明已经是小堆了！
		{
			break;
		}
	}
}

大堆的向下调整算法与小堆类似
不一样的地方：
1. 找出左右孩子较大值
2. 如果父亲小于较大的孩子则交换

2.向上调整算法

先看一个例子：

我们利用向上调整算法：

1. 新插入元素下标为size-1，作为child
2. 利用child去找parent （ parent=(child-1)/2 )
3. 比较child和parent,如果parent 大于 child 那么就交换
4. 然后parent作为新的child 继续迭代
5. 如果 parent 小于等于 child或者parent<=0 那么说明已经走到根了，不用走了

代码实现

//向上调整
void AdjustUp(HPDataType* a,int child)//孩子节点的位置
{
	//孩子节点就是 size-1
	//首先需要找到父节点
	int parent = (child - 1) / 2;
	//然后比较孩子和父亲的大小
	//结束条件就是：孩子节点大于0 如果孩子等于0 说明走到了堆顶
	while ( child > 0 )
	{
		if (a[child] < a[parent])
		{
			//如果孩子比父亲小 那么进行交换
			Swap(&(a[child]), &(a[parent]));
			//然后更新child和parent
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

2. 堆的创建

给你一个数组，这个数组逻辑上可以看作一个完全二叉树，但是还不是一个堆，那么如何把它变成一个堆呢？
我们都以建小堆为例

① 向上调整建堆

int arr[]={70,56,30,25,15,10};

显然这是一个大堆，怎么建立成一个小堆呢？

1. 从数组的第二个元素开始（即 i=1 ），因为根节点是最顶部，无法向上调整
2. parent=(child-1)/2,找出父亲下标
3. 父亲与孩子比较，如果孩子小于父亲，那么二者交换
4. 然后数组坐标向后走，重复刚才过程
5. 直到数组走到尽头

代码

void CreateHeap(int* a,int n)
{
	//从i=1开始 因为i=0不需要向上调整
	for (int i = 1; i < n; i++)
	{
		AdjustUp_small(a, i);
	}
}

② 向下调整建堆

1. 从最后一个非叶子节点开始作为parent(因为最后一个非叶子节点一定是最后一个节点的父亲）
2. 如果child
3. 如果child>=size ,停止调整进入下一次( i --）即前一个非叶子节点作为parent

代码

void CreateHeap(int* a,int n)
{
	//向下调整建堆
	// 注意： 要从最后一个非叶子节点开始调， 因为这是向下调整，
	//我们找的是parent 叶子节点下面没有节点！
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown_big(a, n, i);
		//其中i是每一次的父节点！
	}
}

3. 建堆的时间复杂度分析 ① 向下调整建堆的时间复杂度

我们是利用深度h来计算出大概的移动次数
换算成用节点数n表示，约为O（n)

② 向上调整建堆的时间复杂度

所以 向上调整建堆的时间复杂度达到了 O( N*logN）

对比之下：显然向下调整建堆的效率更高

4. 堆的插入

由于堆是用数组实现的，所以堆的插入分两步

1. 对数组扩容，把插入数据放到数组末尾
2. 把最后一个数据向上调整，使插入数据后仍然保持一个堆

代码

//push--先插入到最后面
void HPNodePush(HP* ph, HPDataType x)
{
	assert(ph);
	//首先要检查是否需要扩容
	if (ph->size == ph->capacity)
	{
		int newCapacity = ph->capacity == 0 ? 4 : 2 * (ph->capacity);
		HPDataType* tmp = (HPDataType*)realloc(ph->a, sizeof(HPDataType) * newCapacity);
		//如果扩容失败 异常退出
		if (tmp == NULL)
		{
			printf("realloc fail!");
			exit(-1);
		}
		ph->a = tmp;
		//扩容成功 更新容量的大小
		ph->capacity = newCapacity;
	}
	// 那么直接插入x
	ph->a[ph->size] = x;
	ph->size++;
	//我们只是插入了 x
	//但是还需要调整 使其满足堆的结构！
	AdjustUp(ph->a,ph->size-1);

}

5. 堆的删除

堆的删除是指删除掉堆顶的数据
可是删除之后堆顶的数据变成什么？
堆需要一直保持是一棵完全二叉树呀！
我们直观的想法就是：堆由数组实现，所以只需要把数组后面的数据向前挪动不就好了

但是这样存在两个问题：

1. 堆原来的结构被破坏了！原来的兄弟变成了父子，关系全乱了！
   
2. 即使是正确的，由于挪动数据也存在O(N)的时间复杂度

所以这种思路是不对的！
要删除数据：

1. 把堆顶数据和末尾数据交换
2. 然后把最后一个数据删除(–size) —> 这样其实就把堆顶的数据从堆里删除了
3. 然后 最后一个数据到了堆顶，此时已经不是堆了，我们只需要把他调整成堆

采用向下调整

例：

代码：

void HPNodePop(HP* ph)
{
	assert(ph);
	//首先交换堆顶和最后一个位置的数据
	Swap(&(ph->a[0]), &(ph->a[ph->size-1]));

	//然后size--就相当于删除了原来的堆顶元素

	ph->size--;

	//然后需要向下调整
	AdjustDown(ph->a, ph->size, 0);

}

6. 取堆顶数据

直接返回数组下标为0的位置的元素即可
但是要注意：需要检查堆是不是空

//获取堆顶元素
HPDataType HPNodeTop(HP* ph)
{
	assert(ph);
	//获取堆顶元素 其实就是获得下标为0的元素
	//因为这是小堆
	//获取堆顶元素 前提是 堆中有元素
	assert(ph->size > 0);
	return ph->a[0];
}

7. 堆的判空

堆是利用了顺序表，顺序表中含有一个size记录元素个数
size为0则堆为空

//判空
bool HPNodeEmpty(HP* ph)
{
	assert(ph);
	return ph->size == 0;
}

8. 堆元素个数

size 记录了元素的个数

//堆的元素个数
int HPNodeSize(HP* ph)
{
	assert(ph);
	return ph->size;
}

堆的销毁

因为堆中有我们malloc的数组，所以主要是释放数组空间
同时把size和capacity置0

//销毁
void HPNodeDestory(HP* ph)
{
	assert(ph);
	free(ph->a);
	ph->size = ph->capacity = 0;
	ph->a = NULL;
}

三、堆的应用. 1. 堆排序 前言

首先我们可以利用堆进行升序/降序打印，但是这都是直接打印出来的，原来的数组并没有发生变化
如何利用堆把数组排成升序/降序呢？

那么如何把打印改成排序呢？
我们可以利用堆，上面只需要把打印的操作换成赋值

//空间复杂度为O（n)
void HeapSort_useless(int* a, int n)
{
	HP hp;
	HPNodeInit(&hp);
	//把数组中的元素全部push到堆
	for (int i = 0; i < n; i++)
	{
		HPNodePush(&hp, a[i]);
	}

	int i = 0;
	while (!HPNodeEmpty(&hp))
	{
		a[i++] = HPNodeTop(&hp);
		HPNodePop(&hp);
	}

	//别忘了释放内存
	//因为堆里面也创建了一个数组，需要释放否则 容易内存泄漏！
	HPNodeDestory(&hp);
}

不过该方法存在很明显的缺陷：

1. 我们需要先写一个堆的数据结构
2. 需要O（n)的时间复杂度

所以我们在实现堆排序的时候，直接把数组创建成堆就可以了
在所建的堆上进行操作，就不用开辟空间和创建数据结构了
创建堆 有两种方式：

1. 向下调整建堆
2. 向上调整建堆

考虑到建堆的时间复杂度，我们选择更优向下调整建堆

利用堆排升序（易错！)

如果实现堆排序 升序，那么使用大堆还是小堆？

- - -优先使用大堆！

使用小堆可能让我们产生错误的思路：
一开始我们会觉得，排升序建小堆，因为依次把最小的取出来就是排完序了

我们这里使用大堆：

其实利用小堆也采用这样的思路也可以实现升序，只不过因为 堆排序就是利用堆顶进行排序
而小堆的顶是最小元素，容易让我们直接想把堆顶取出来而产生错误的思路，所以尽量用大堆

代码

void HeapSort(int* a,int n)
{
	
	//向下调整建大堆:
	// 注意： 要从最后一个非叶子节点开始调， 因为这是向下调整，我们找的是parent 叶子节点下面没有节点！
	//最后一个非叶子节点就是最后一个节点(n-1)的父亲
	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);
		//然后把最后一个数据的下标减一下！
		--end;
		//直到end到堆顶的时候 就不需要调整了

	}
	 
}

2. TOP k问题

我们经常在生活中看到，全省100强，全市50强等字眼
这就是经典的TOP k问题

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

那么怎么找出数据中 前k大或者前k小的数据呢？

1. 对数据进行排序，然后取前k个 ----> O(N*logN)
2. 建一个把所有数据建立一个大堆/小堆，然后top/pop k次 O(N+K*logN)

这两种方法在数据量不是很大的时候都可以
但是如果数据量非常庞大，比如如果有100亿呢？如何求Top k？

方法：

//找出最大的k个数 并打印
void PrintKMax(int* a, int n, int k)
{
	//1.首先利用 a中的前k个元素建小堆
	int* kMinHeap = (int*)malloc(sizeof(int) * k);
	assert(kMinHeap);
	//把数组a中的前k个数据放到kMinHeap中 
	for (int i = 0; i < k; ++i)
	{

		kMinHeap[i] = a[i];
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(kMinHeap, k, i);
	}
	//2.然后遍历剩下的n-k个数 如果大于堆顶数据 就交换然后调整
	for (int j = k; j < n; ++j)
	{
		if (a[j] > kMinHeap[0])
		{
			kMinHeap[0] = a[j];
			AdjustDown(kMinHeap, k, 0);//向下调整保持小堆
		}
	}

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

}

void testTopk()
{
	int n = 10000;
	//开辟一万个元素的数组
	int* a = (int*)malloc(sizeof(int) * n);
	assert(a);
	srand((unsigned int)(time(NULL)));
	for (int i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[100] = 1000000 + 1;
	a[1000] = 1000000 + 3;
	a[2562] = 1000000 + 10;
	a[1547] = 1000000 + 8;
	a[1001] = 1000000 + 7;
	a[784] = 1000000 + 2;
	a[1123] = 1000000 + 4;
	a[989] = 1000000 + 9;
	a[9999] = 1000000 + 6;
	a[1024] = 1000000 + 5;
	PrintKMax(a,n,10);
}
int main()
{
	testTopk();
	return 0;
}

测试：

---

感谢阅读~ 留下你的三连~