admin管理员组

文章数量:1442841

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

前言

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

1. 堆的概念与结构

如果有⼀个关键码的集合，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜：

K=\{ k_0,k_1,k_2,...,k_{n-1} \}

，i = 0、1、2...，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

1.2 堆的重要性质

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

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

2. 堆的实现

原码自取gitee

现在我们知道，完全二叉树的顺序结构就是堆，顾名思义，堆就是用顺序表（数组）实现的。

Heap.h

代码语言：javascript代码运行次数：0运行复制
#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 向上调整算法

该算法辅助实现堆的插入

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

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

代码语言：javascript代码运行次数：0运行复制
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 堆的插入
  • 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后
  • 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可
代码语言：javascript代码运行次数：0运行复制
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};

向下调整过程图

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

代码核心：

  1. 父亲与孩子的下标关系：child=2*parent + 1
  2. 孩子的下标小于n，避免数组越界访问
代码语言：javascript代码运行次数：0运行复制
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 堆的删除

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

  • 将堆顶元素与堆中最后⼀个元素进⾏交换
  • 删除堆中最后⼀个元素
  • 将堆顶元素向下调整到满⾜堆特性为⽌
代码语言：javascript代码运行次数：0运行复制
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层

则需要移动结点总的移动步数为：每层结点个数乘向下调整次数

T(h) = 2^0*(h-1)+ 2^1*(h-2)+2^2*(h-3)+2^3*(h-4)+……+2^{h-3}*2+2^{h-2}*1

利用数列的错位相减（计算步骤如下图）

得出：

T(h) = 2^h −1 − h

根据⼆叉树的性质：

n = 2^h-1和h=log_2(n+1)

得出：

T(n)=n-log_2(n+1)≈n

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

3.2 向上调整时间复杂度(
n*logn

)

与向下调整类似，计算所有结点向上移动至堆顶的移动总次数即可 设树的高度为h 我们需要计算的是向上移动的总次数T(n)

分析： 第1层，

2^0

个结点，需要向下移动0层 第2层，

2^1

个结点，需要向下移动1层 第3层，

2^2

个结点，需要向下移动2层 第4层，

2^3

个结点，需要向下移动3层 … 第h层，

2^{h-2}

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

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

T(h) = 2^1*1+2^2*2+2^3*3+……+2^{h-2}*（h-2）+2^{h-1}*(h-1)

也是利用数列的错位相减得：

T(h) = -(2^h-1)+2^h * （h-1）+2^0

根据⼆叉树的性质：

n = 2^h-1和h=log_2(n+1)

得出：

T(n)=(n + 1)(log_2(n +1) − 2) + 2≈n*log_2n

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

n*logn
3.3 结论

由此可见，向下调整的效率是优于向上调整的，所以我们以后需要建堆时，应该优先考虑向下调整建堆。再后面的堆排序中我们可以深刻体会到。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-03-22，如有侵权请联系 cloudcommunity@tencent 删除链表数组算法二叉树数据结构

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

版权声明：本文标题：【初探数据结构】二叉树的顺序结构——堆的实现详解（上下调整算法的时间复杂度分析） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/biancheng/1748069677a2801901.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。