【数据结构】堆问题详解（堆基本操作，向上向下调整，堆排序，TopK问题）

目录

• 堆的概念及结构性质
  ⚪概念
  ⚪性质/思路
• 堆的实现
  ⚪头文件
  ⚪初始化堆
  ⚪销毁堆
  ⚪打印堆
  ⚪Push插入元素
  ⚪向上调整
  ⚪Pop删除元素
  ⚪向下调整
  ⚪返回堆顶
  ⚪判断是否为空
  ⚪返回堆大小
• 堆排序
  ⚪升序 - 小堆
  ⚪升序 - 大堆（降序 - 小堆）
• TopK问题

堆的概念及结构性质

概念

堆（Heap）是一种经典的树形数据结构，它是一棵完全二叉树，其每个节点的键值都不小于或不大于其左右子节点的键值，我们称之为“堆属性”。

根据堆属性，堆被分为两种类型。

大根堆（Max Heap）：父节点的键值大于等于任何一个子节点的键值。
小根堆（Min Heap）：父节点的键值小于等于任何一个子节点的键值。

性质

• 堆中某个节点的值总是不大于或不小于其父节点的值（即堆必然是大根堆或小根堆）
• 堆总是一棵完全二叉树。

堆的实现思路：

正如上图所示，堆的结构一般使用数组（内存连续、索引简单等）。

有了底层结构，剩下的就是功能上的实现了。

堆的实现

头文件

• 头文件展示堆的相关功能。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HPDataType;

//创建堆结构体
typedef struct heap {
	HPDataType* a;//定义数组
	int size;//定义堆大小（当前数据元素）
	int capacity;//定义堆容量（最大元素个数）
}HP;

//初始化堆
void HeapInit(HP* hp);
//销毁堆
void HeapDestroy(HP* hp);
//打印堆（便于测试观察）
void HeapPrint(HP* hp);

//交换元素
void Swap(HPDataType* p1, HPDataType* p2);
//堆插入元素
void HeapPush(HP* hp, HPDataType x);
//堆删除元素
void HeapPop(HP* hp);

//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//向上调整
void AdjustUp(HPDataType* a, int child);

//判断堆是否为空
bool HeapEmpty(HP* hp);
//堆大小
int HeapSize(HP* hp);
//返回堆顶
HPDataType HeapTop(HP* hp);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

初始化堆

• 最基本的功能，将结构体里的成员变量初始化即可。

void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
1
2
3
4
5
6

---

销毁堆

• hp->a是否置空无影响。
• 将堆结构体的指针销毁。

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->capacity = hp->size = 0;
}
1
2
3
4
5
6

---

打印堆

• 主要为了便于测试于观察后续代码的使用，用for循环遍历数组，执行printf() 语句打印信息

void HeapPrint(HP* hp)
{
	assert(hp);
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

---

插入元素

• 先判断 是否需要扩容 ，完毕后进行插入操作。
• 插入操作：创建堆节点，realloc分配空间，判断是否成功，如果成功则进行变量更新。
• 最后进行 向上调整 ，保证堆的结构。

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	//判断扩容
	if (hp->size == hp->capacity)
	{
		// 如果堆为空则赋值capacity，堆不为空则扩充一倍
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);//将a扩容
		if (tmp == NULL) // 判断realloc是否成功
		{
			perror("realloc fail");
			exit(-1);
		}
	
		//  更新容量
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	// 插入元素
	hp->a[hp->size] = x;
	hp->size++;

	AdjustUp(hp->a, hp->size - 1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

向上调整

• 向上排序的意义：在我们每次进行插入操作后，为了保证堆结构不变（仍是大堆/小堆），所以需要进行向上调整
• 首先找到数组最后一个元素的父节点，在数组中为parent = (child - 1) / 2，如果子节点<父节点 （以小堆为例，如果再if语句选用’>'则为大堆） ，则交换两节点，再将父节点设为子节点循环往复将该堆重新置为小堆

//元素交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//不用while(parent >= 0)//因为parent永远不为负
	while (child > 0)
	{
		if (a[child] < a[parent])//a[child] > a[parent] -> 大堆
		{
			//交换子节点父节点，并将父节点置为子节点
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

删除元素

• 将首元素于末尾元素交换随后进行向下调整，重点在于向下调整

void HeapPop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));//堆不能为空
	
	//交换元素
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

	AdjustDown(hp->a, hp->size, 0);
}
1
2
3
4
5
6
7
8
9
10
11

---

向下调整

• 向下调整是从父节点向下，所以定义子节点（这里我们选用左子节点）
• 确保小堆则需要child指向更小的孩子，之后比较如果a[child] < a[parent]则交换并且把parent变为child

void AdjustDown(HPDataType* a, int n, int parent) 
{
	int child = parent * 2 + 1;//左子节点
	while (child < n)
	{
		//确保child指向更小的孩子
		if (child + 1 < n && a[child + 1] < a[child])//右孩子存在且右小于左 /* a[child + 1] > a[child]大堆 */
		{
			child++;//将child改为右子节点
		}
		//孩子是否小于父节点 <==> 是否应该继续交换
		if (a[child] < a[parent]) //a[child] > a[parent]大堆
		{
		
		Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

返回堆顶

• 先判断hp不为空（存在堆顶元素），直接返回a[0]即堆顶

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);
	return hp->a[0];//堆顶
}
1
2
3
4
5
6

---

判断是否为空

• bool类型直接返回表达式即可

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;//bool类型直接返回表达式hp->size == 0
}
1
2
3
4
5

返回堆大小

• 堆大小即size大小

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;//直接返回size
}
1
2
3
4
5

---

堆排序

堆排序通常情况如果排升序则建大堆，排降序建小堆。

---

升序 - 小堆

下面用小堆排升序是可行的，但效率较低

//升序 - 小堆，效率低
//O(N^2)
void HeapSort1(HPDataType* a, int n)
{
	HP hp;
	HeapInit(&hp);
	// 将每个元素插入到小根堆中
	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp, a[i]);
	}
	
	//Pop 小堆的大小次数
	for (int i = 0; i < n; i++)
	{
		// 每次取出小根堆的堆顶元素（最小元素），插入到数组中
		a[i] = HeapTop(&hp);
		HeapPop(&hp); // pop函数会自动执行向下调整，保证每次取到最小值
	}

	HeapDestroy(&hp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

升序 - 大堆（换成小堆则降序）

• 先把数组放到大堆，然后将堆顶(最大的数)与最后一个数交换
  ，再向下调整选出次小数，循环往复。

//升序 - 使用大堆，效率高
//若使用小堆则为降序
//(O*log*N)
void HeapSort(int* a, int n)
{
	//把数组变成小堆
	//法一 - 通过向上调整将数组构建成小堆
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	
	//法二 - 向下调整
	int parent = (n - 1 - 1) / 2; 
	for (int i = parent; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

	// 不断选择堆顶元素并调整堆
	for (int end = n - 1; end > 0; end--)
	{
		// 将堆顶元素（最小元素）与数组首位交换
		Swap(&a[end], &a[0]);
		//	再次调堆（数组），选出次小数
		AdjustDown(a, end, 0);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

TopK问题

TopK问题即在一个n个数的序列中找到最大的前K个元素；

• 首先给数组开辟一个sizeof(int) * n的空间，将数组a里的所有元素随机填入[0, n]范围内的数字，再手动设置k个大于n的数，最后PrintTopk则完成测试代码。

//Topk问题例子
//找n个数字中最大的前k个（令k等于10）
void TestTopK()
{
	int n = 10000;
	int k = 10;
	int* a = (int*)malloc(sizeof(int) * n);
	if (a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	srand(time(0));
	for (size_t i = 0; i < n; i++)
	{
		a[i] = rand() % 1000000;//随机设置n个在[0, 1000000]范围内的数字
	}
	//设置10个大于100w的数字
	a[4] = 1000000 + 4;
	a[1231] = 1000000 + 1;
	a[114] = 1000000 + 5;
	a[514] = 1000000 + 2;
	a[1919] = 1000000 + 3;
	a[810] = 1000000 + 8;
	a[571] = 1000000 + 6;
	a[414] = 1000000 + 7;
	a[2333] = 1000000 + 9;
	a[9999] = 1000000 + 10;
	PrintTopk(a, n, k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 建立小堆，将前k个元素存入小堆中，将剩下的n-k的元素与堆顶元素比较，留大的，然后进行向下调整（大的数都会沉在堆底），即可实现找到最大的k个数。

void PrintTopk(int* a, int n, int k)
{
	HP hp;
	HeapInit(&hp);

	//先把前k位存在小堆中
	for (int i = 0; i < k; i++)
	{
		HeapPush(&hp, a[i]);
	}
	//剩下N-K个数字与堆顶数据比较，谁大留谁
	for (int i = k; i < n; i++)
	{
		if (a[i] > HeapTop(&hp))
		{
			//法一
			//将堆顶的元素删掉，把a[i]放入堆顶
			//HeapPop(&hp);
			//HeapPush(&hp, a[i]);
			
			//把a[i]放入
			hp.a[0] = a[i];
			AdjustDown(hp.a, hp.size, 0);
		}
	}
	HeapPrint(&hp);
	HeapDestroy(&hp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28