当前位置：首页 > article >正文

【初探数据结构】二叉树的顺序结构——堆的实现详解（上下调整算法的时间复杂度分析）

article 2025/3/22 9:12:34

💬 欢迎讨论：在阅读过程中有任何疑问，欢迎在评论区留言，我们一起交流学习！
👍 点赞、收藏与分享：如果你觉得这篇文章对你有帮助，记得点赞、收藏，并分享给更多对数据结构感兴趣的朋友

文章目录

- 前言
- 1. 堆的概念与结构
- - 1.2 堆的重要性质
- 2. 堆的实现
- - 2.1 堆的插入+向上调整算法
  - - 2.1.1 向上调整算法
    - 2.1.2 堆的插入
  - 2.2 堆的删除+向下调整算法
  - - 2.2.1 向下调整算法
    - 2.2.2 堆的删除
- 3. 复杂度分析（向上调整与向下调整）

前言

堆是一种基于完全二叉树的数据结构，通常分为最大堆（父节点值≥子节点）和最小堆（父节点值≤子节点）。由于完全二叉树的特性，堆可以用数组高效存储，通过索引关系快速定位父子节点。

1. 堆的概念与结构

如果有⼀个关键码的集合，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜： $K=\{ k_0,k_1,k_2,...,k_{n-1} \}$ ，i = 0、1、2...，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

在这里插入图片描述

1.2 堆的重要性质

对于具有n个结点的完全二叉树，如果按照从上至下、从左至右的数组顺序对所有结点从0开始编号，对于序号为i的结点有：

若i > 0，i位置结点的双亲序号为：（i - 1）/2; 当i为0时，i为根结点。
若2i + 1 < n，左孩子序号：2i + 1；如果2i + 1 >=n，则无左孩子
若2i + 2 < n，左孩子序号：2i + 2；如果2i + 2 >=n，则无右孩子

2. 堆的实现

原码自取gitee

现在我们知道，完全二叉树的顺序结构就是堆，顾名思义，堆就是用顺序表（数组）实现的。
在这里插入图片描述
Heap.h

#pragma once

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

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//堆
	int size;//堆的大小
	int capacity;//堆的容量
}HP;
//堆的初始化
void HeapInit(HP* php);
// 堆的销毁
void HeapDestory(HP* php);
// 堆的插入
void HeapPush(HP* php, HPDataType x);
// 堆的删除
void HeapPop(HP* php);
// 取堆顶的数据
HPDataType HeapTop(HP* php);
// 堆的数据个数
int HeapSize(HP* php);
// 堆的判空
int HeapEmpty(HP* php);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//向上调整
void AdjustUp(HPDataType* a, int child);
//交换
void swap(HPDataType* p1, HPDataType* p2);

声明：本文以实现小堆为例，如需实现大堆，修改小堆调整算法的条件即可，这里不过多赘述。

2.1 堆的插入+向上调整算法

2.1.1 向上调整算法

该算法辅助实现堆的插入

将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。

在这里插入图片描述
仔细观察这个图解，不难发现：从某个结点出发，与其父亲比较，如果小于他的父亲，就交换位置；如果大于或等于就不动，调整结束。

void AdjustUp(HPDataType* a,int child)
{
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[child] > a[parent]) {
			swap(&a[child],&a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

2.1.2 堆的插入

先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后
插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可

在这里插入图片描述

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//若空间不足，则扩容
	if (php->size == php->capacity) {
		HPDataType* ptr = realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
		if (ptr == NULL) {
			perror("realloc fail");
			exit(-1);
		}
		php->a = ptr;
		php->capacity *= 2;
	}
	php->a[php->size] = x;
	AdjustUp(php->a, php->size);
	php->size++;
}

2.2 堆的删除+向下调整算法

2.2.1 向下调整算法

该算法辅助实现堆的删除

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

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

向下调整过程图
仔细观察这个图解，不难发现：从根结点出发，与其较小的孩子比较，如果小于这个孩子，就交换位置；如果大于或等于就不动，调整结束。

代码核心：

父亲与孩子的下标关系：child=2*parent + 1
孩子的下标小于n，避免数组越界访问

void AdjustDown(HPDataType* a,int n,int parent)
{
	int child = 2 * parent + 1;
	while (child < n) {
	// 假设法，选出左右孩⼦中⼩的那个孩⼦
		if (a[child] < a[child + 1] && child + 1 < n){
			child++;
		}
		if (a[parent] < a[child]) {
			swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else break;
	}
}

2.2.2 堆的删除

删除时需注意判断堆是否为非空，若对空堆进行删除，必然出错。

将堆顶元素与堆中最后⼀个元素进⾏交换
删除堆中最后⼀个元素
将堆顶元素向下调整到满⾜堆特性为⽌

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	swap(php->a,&php->a[php->size-1]);
	php->size--;
	AdjustDown(php->a,php->size, 0);
}

其余的初始化、销毁、判空等等，非常简单，都是老套路了，这里留给读者自己发挥。
在我过去的一些文章都有类似的详解（顺序表、链表、栈、队列）。大家可以照猫画虎。

传送门呈上~
【初探数据结构】线性表———顺序表的详解和实现
【初探数据结构】线性表————链表（一）（单链表的实现）
【初探数据结构】线性表——链表（二）带头双向循环链表（详解与实现）
【初探数据结构】线性表——栈与队列（代码实现与详解）

3. 复杂度分析（向上调整与向下调整）

因为堆是完全二叉树，而满二叉树也是完全二叉树，为了简化证明，此出以满二叉树为研究对象。(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)

3.1 向下调整时间复杂度（ $O （ N ）$ ）

最坏的情况是什么呢？
就是树的每个结点全部都要进行一次调整堆底。
设树的高度为h
我们需要计算的是向下移动的总次数T(n)
在这里插入图片描述
分析：
第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层