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

引言

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

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

一、基本概念

1.1堆的概念

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

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

1.2堆的存储结构

堆通常使用数组进行存储，这种方式的优点是可以直接通过数组下标计算父节点和子节点的位置：

数组索引映射： 对于节点 i： 父节点：parent(i) = (i - 1) / 2（使用整数除法） 左子节点：left(i) = 2 * i 1 右子节点：right(i) = 2 * i 2

代码语言：javascript复制

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

存储示例 假设堆的数组表示为 {9，8，6，6，7，5，2，1，4，3，6，2}： 7的索引是4，其父节点为8(索引1)，左子节点为3(索引9)，右子节点6(索引10)。

这种方式有效利用了内存，避免了指针的开销。

1.3堆的特点

堆作为完全二叉树的一个特例，具有以下特性。

‧ 最底层节点靠左填充，其他层的节点都被填满。

‧ 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。

‧ 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。

二、 堆的基本操作

2.1初始化

代码语言：javascript复制

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

2.2创建堆

创建堆通常有两种方式：

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

代码语言：javascript复制

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

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

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

代码语言：javascript复制

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)

代码实现：

代码语言：javascript复制

//插入
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)

代码实现：

代码语言：javascript复制

//删除,出堆顶数据
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）： 用于插入操作。当新插入的元素大于（或小于）其父节点时，通过交换将其上移，直至堆性质满足。

代码语言：javascript复制

//堆的向上调整
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）： 用于删除操作和堆化。根节点（或其他节点）与其子节点进行比较，将其值与较大的子节点（或较小的子节点）进行交换，直至堆性质满足。

代码语言：javascript复制

//堆的向下调整
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，堆为空，反之则非空。

代码语言：javascript复制

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

2.7获取堆顶元素

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

代码语言：javascript复制

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

三、堆的常见应用

1. 优先队列

优先队列是一种数据结构，允许根据优先级处理元素。堆可以高效地实现优先队列，支持在 O(logn) 时间内插入和删除元素，适用于任务调度和图算法（如 Dijkstra 算法）。

2. 堆排序

堆排序是一种基于堆的排序算法，时间复杂度为 O(nlogn)。它通过构建最大堆并逐步提取最大元素来实现排序，适合需要原地排序的场景。

3. Top-k 问题

Top-k 问题涉及从数据集中找出前 k 个最大或最小的元素。使用最小堆可以在 O(nlogk) 的时间复杂度内有效解决该问题，常用于数据分析和排行榜。

4. 图论中的应用

在图算法中，堆常用于 Dijkstra 和 Prim 算法，通过优先队列高效管理节点和边，从而加速最短路径和最小生成树的计算。

下面我们来详细讲一下 Top-k问题。

四、Top-k问题精讲

方法一：遍历选择

我们可以进行