数据结构--堆的深度解析

目录

引言

一、基本概念

1.1堆的概念

1.2堆的存储结构

1.3堆的特点

二、 堆的基本操作

2.1初始化

2.2创建堆

2.3插入元素 

2.4删除元素 

2.5堆化操作

2.6堆的判空

2.7获取堆顶元素

三、堆的常见应用

1. 优先队列

2. 堆排序

3. Top-k 问题

4. 图论中的应用

四、Top-k问题精讲 

方法一：遍历选择

方法二：排序

 方法三：最小堆法

总结

引言

堆（Heap）是一种非常重要的非线性数据结构，广泛应用于各种算法和问题解决中，如优先队列、堆排序、Top-k 问题等。本文将深入解析堆的定义、类型、操作、应用及其优缺点。

在上篇博客我们简单介绍了堆，并用堆实现了二叉树的顺序存储，这里我们趁热打铁深入解析堆这种结构。

一、基本概念

1.1堆的概念

堆是一种特殊的完全二叉树，具有以下性质：

• 完全二叉树：堆是一个完全二叉树，意味着树的每一层都被完全填满，除了最后一层可能没有填满，但所有节点都集中在左侧。
• 堆性质：堆有两种类型：
  ‧ 小顶堆（min heap）：任意节点的值 ≤ 其子节点的值。
  ‧ 大顶堆（max heap）：任意节点的值 ≥ 其子节点的值。

//定义堆的结构--数组
typedef int DataType;
typedef struct Heap//小堆为例
{
	DataType *arr;
	int size;
	int capacity;
}HP;

二、 堆的基本操作

2.1初始化

//初始化
void HPInit(HP* p)
{
	assert(p);
	p->arr = NULL;
	p->size = p->capacity = 0;
}

2.2创建堆

创建堆通常有两种方式：

1.逐步插入：
从一个空堆开始，逐个插入元素。每插入一个新元素后，使用“上浮”操作来维持堆的性质。

for (int i = 0; i < n; i++)
{
	AdjustUp(arr, i);//向上调整算法，2.5中右有详细说明
}

2.堆化（Heapify）：
给定一个无序数组，可以通过一次性构建堆来提高效率。这通常采用自底向上的方法，(先假定这组数据是一个“堆结构”)从最后一个非叶节点开始，逐个进行“下沉”操作，使之调整为堆(真正具有堆的特性)。

堆化算法步骤：
对于索引 i 从 (n-1-1)/2 到 0 进行下沉操作，n 是数组的长度。

for (int i =(n-1-1)/2 ; i >= 0; i--)//n-1为数组最后一个数据的下标，(n-1-1)/2为其父节点
{
	AdjustDown(arr, i, n);//向下调整算法，2.5中右有详细说明
}

2.3插入元素 

在堆中插入元素的步骤如下：

1.添加元素：
将新元素添加到堆的末尾（数组的最后一个位置）。

2.上浮操作：
比较新元素与其父节点的值，如果新元素大于父节点（在最大堆中）或小于父节点（在最小堆中），则交换两者，并继续上浮直到堆性质得以恢复。
时间复杂度：O(log n)

代码实现：

//插入
void HPPush(HP* p, DataType x)
{
	assert(p);
	if (p->size == p->capacity)//判断空间是否足够
	{
		//扩容
		int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;
		DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));
		if (tmp == NULL) 
		{
			perror("realloc fail!");
			exit(1);
		}
		p->arr = tmp;
		p->capacity = NewCap;
	} 
	p->arr[p->size] = x;
	AdjustUp(p->arr, p->size);
	++p->size;
}

2.4删除元素 

到通常，删除操作是从堆中移除根节点（最大或最小值），其步骤如下：
1.替换根节点：
将根节点（堆顶）替换为最后一个元素，然后从数组中删除该元素。
2.下沉操作：
从根节点开始，依次将该节点与其子节点进行比较，将其值与较大的子节点（在最大堆中）或较小的子节点（在最小堆中）进行交换，直堆的性质恢复。
时间复杂度：O(log n)

 代码实现：

//删除,出堆顶数据
void HPPop(HP* p)
{
	assert(p && p->size);
	Swap(&p->arr[0], &p->arr[p->size - 1]);
	--p->size;
	AdjustDown(p->arr, 0, p->size);
}

2.5堆化操作

堆化操作是保持堆性质的关键，主要包括：
1.向上调整（AdjustUp）：
用于插入操作。当新插入的元素大于（或小于）其父节点时，通过交换将其上移，直至堆性质满足。

//堆的向上调整
void AdjustUp(DataType* arr, int child)
{
	int parent = (child - 1) / 2;//父节点
	while(child>0)//注意child可能会被调整到根节点，这时候就不能再调整了
	{
		//建小堆  <  //建大堆  >
		if (arr[child] < arr[parent])//如果条件语句不成立，就说明堆已经成型
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;//循环以上步骤
		}
		else
		{
			break;
		}
	}
}

计算向上调整算法建堆时间复杂度

因为堆是完全⼆叉树，⽽满⼆叉树也是完全⼆叉树，此处为了简化使⽤满⼆叉树来证明(时间复杂度本来看的就是近似值，多⼏个结点不影响最终结果)

分析：

第1层， 2^0 个结点，需要向上移动0层

第2层， 2^1 个结点，需要向上移动1层

第3层， 2^2 个结点，需要向上移动2层

第4层， 2^3 个结点，需要向上移动3层

......

第h层， 2^(h-1) 个结点，需要向上移动h-1层

则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）

由此可知，

向上调整算法建堆时间复杂度为：O(n ∗ log2 n)

2.向下调整（AdjustDown）：
用于删除操作和堆化。根节点（或其他节点）与其子节点进行比较，将其值与较大的子节点（或较小的子节点）进行交换，直至堆性质满足。

//堆的向下调整
void AdjustDown(DataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	while (child < n) 
	{
		//小堆：寻找左右孩子最小的那个
		//大堆：寻找左右孩子最大的那个
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		//这里和向上调整就一样了，比较，交换，循环
		//建小堆  <   //建大堆  >
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

计算向下调整算法建堆时间复杂度

分析：

第1层， 2^0 个结点，需要向下移动h-1层

第2层， 2^1 个结点，需要向下移动h-2层

第3层， 2^2 个结点，需要向下移动h-3层

第4层， 2^3 个结点，需要向下移动h-4层

......

第h-1层， 2^(h-2) 个结点，需要向下移动1层

由此可知，

向下调整算法建堆时间复杂度为：O(n)

2.6堆的判空

堆的大小为0，堆为空，反之则非空。

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

2.7获取堆顶元素

获取堆的根节点（最大或最小值）非常简单，只需返回数组的第一个元素。

//返回堆顶元素
DataType HPTop(HP* p)
{
	assert(p && p->size);
	return p->arr[0];
}

四、Top-k问题精讲 

方法一：遍历选择

方法二：排序

 方法三：最小堆法

1. 初始化一个小顶堆，其堆顶元素最小。

2. 先将数组的前 𝑘 个元素依次入堆。

3. 从第 𝑘 + 1 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。

4. 遍历完成后，堆中保存的就是最大的 𝑘 个元素。

 代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

// 堆的结构
typedef struct Heap
{
	DataType* arr;
	int size;
	int capacity;
} HP;

// 交换两个元素
void Swap(DataType* x, DataType* y)
{
	DataType tmp = *x;
	*x = *y;
	*y = tmp;
}
// 向下调整堆
void AdjustDown(DataType* arr, int parent, int n)
{
	int child = parent * 2 + 1; // 左孩子
	while (child < n) {
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[child] < arr[parent]) {
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 建小堆
void BuildMinHeap(int* arr, int k)
{
	for (int i = (k-1-1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, k);
	}
}

// 查找Top-k元素
void FindTopK(DataType* arr, int n, int k) {
	if (k <= 0 || k > n)
	{
		printf("k的值非法\n");
		return;
	}

	//开辟所需小堆的内存
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}

	// 将前k个元素放入小堆
	for (int i = 0; i < k; i++)
	{
		minheap[i] = arr[i];
	}
	BuildMinHeap(minheap, k);

	// 遍历剩余元素，更新小堆
	for (int i = k; i < n; i++)
	{
		if (arr[i] > minheap[0])
		{
			minheap[0] = arr[i]; // 替换堆顶
			AdjustDown(minheap, 0, k); // 重新调整堆
		}
	}

	// 输出Top-k元素
	printf("最大的前%d个元素为:\n", k);
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");

	// 释放内存
	free(minheap);
}

int main() {
	DataType array[] = {1,3,5,7,9,2,4,6,8,10};
	int n = sizeof(array) / sizeof(array[0]);
	int k = 3; // 查找前3个最大的元素

	FindTopK(array, n, k);

	return 0;
}