初阶数据结构（C语言实现）——5.2 二叉树的顺序结构及堆的实现

server/2025/3/17 22:21:50/

1.二叉树的顺序结构及实现

1.1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段

在这里插入图片描述
左图就是完全二叉树的数组存储
右图是非完全二叉树的数组顺序存储，会造成浪费
数组存储不适合，因为会浪费很多空间。数组存储表示二叉树只适合完全二叉树

  • 逻辑结构：想像出来的
  • 物理结构：实实在在的在内存中是如何存储

表示二叉树的值在数组位置中父子下标关系:

  • parent =(child-1)/2
  • leftchild = parent*2+1
  • rightchild = parent*2+2

1.2 堆的概念及结构

如果有一个关键码的集合K = { k0，k1 ，k2 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： ki<=k2*i+1 且 ki <=k2*i+2 ( ki>= k2*i+1且 ki>=k2*i+2 ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。

在这里插入图片描述

小根堆：树中所有父亲都小于或等于孩子
大根堆：树中所有父亲都大于或等于孩子

1.2.1 堆的时间复杂度

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

在这里插入图片描述
因此：堆的时间复杂度为O(N)。

1.3 堆的实现思路（均以大顶堆为例后面实现也是）

  • 难点：你实际操作的是数组，但是你要会画图，清晰的知道你实现的是二叉树。
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
// 堆的插入
void HeapPush(HP* php, HPDataType x);
// 堆的删除
void HeapPop(HP* php);
// 取堆顶的数据
HPDataType HeapTop(HP* php);
// 堆的数据个数
bool HeapEmpty(HP* php);
// 堆的判空
int HeapSize(HP* php);

1.3.0 堆的初始化

初始化，先断言，然后malloc开辟空间，初始化大小和容量

void HeapInit(HP* php)
{assert(php);//断言php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);//开辟初始空间if (php->a == NULL){perror("HeapInit::malloc fail!");return;}php->size = 0;//目前堆内没有数据，所以size = 0php->capacity = 4;//默认初始容量是4
}

1.3.1 堆向上调整算法

  • 在数组上看起来是毫无章法的交换数据，但是把二叉树画出来，就清晰的知道为什么这么换。

在这里插入图片描述

从孩子向上调整，从刚刚插入的数据位置进行调整
结束条件，是我们的最后交换到堆顶，堆顶结点也就是父亲结点>=0，
在这里插入图片描述

  • 向上调整算法代码实现
void swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//根据孩子位置，计算父亲位置while (child > 0)//child = 0,说明parent不存在了,已经到堆顶了{if (a[child] > a[parent]) //当孩子大小大于父亲大小的时候就交换{swap(&a[child], &a[parent]);//因为其他地方也要用到交换，封装了一个交换函数child = parent; //现在把父亲的值给孩子。parent = (child - 1) / 2;//继续计算现在节点的父亲结点，}else//孩子<=父亲 没必要往上走，直接break就行。		{break;}}
}

1.2.1 堆向下调整算法

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

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

在这里插入图片描述

void swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}
void AdjustDown(HPDataType* a, int n ,int parent)
{int child = parent*2+1;//根据父亲位置，计算孩子位置while (child <n)//走到没有孩子的时候，结束，{// 选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child])//必须把child+1<n放前面，否则后面a[child+1]就越界了！{++child;}//交换if (a[child] > a[parent]){swap(&a[child],&a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

1.2.4 堆的插入

先判断是否要扩容
然后进行数据插入
判断是否满足大根堆条件，不满足就要进行交换

  • 先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

在这里插入图片描述

  • 堆的插入代码实现
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容判断if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);if (tmp == NULL){perror("HeapPush::realloc fail!");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;	//在数组尾巴插入数据php->size++;//给size++//封装一个调整函数，在函数内判断是否进行交换，交换就直接换。AdjustUp(php->a,php->size-1);
}
  • 代码验证，打开调试窗口，在监视1中输入ph.a，5，就能看到我们插入的堆的值。看着数组值自己手动画图，就能看到我们的大顶堆成功实现了。

在这里插入图片描述

1.2.5 堆的删除

  • 删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

在这里插入图片描述

  • 堆的删除代码实现
void HeapPop(HP * php)
{assert(php);assert(!HeapEmpty(php));//删除数据//（1）交换堆顶和最后一个数据 直接删掉。swap(&php->a[0], &php->a[php->size-1]);php->size--;//新的堆顶元素向下调整AdjustDown(php->a, php->size,0);
}

1.2.6 其他

HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}
  • 验证。调试，在监控窗口输入：hp.a，3

在这里插入图片描述

2 附录：堆的代码实现

2.1 20250312_heap.h

#pragma once
#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* php);
// 堆的插入
void HeapPush(HP* php, HPDataType x);
// 堆的删除
void HeapPop(HP* php);
// 取堆顶的数据
HPDataType HeapTop(HP* php);
// 堆的数据个数
bool HeapEmpty(HP* php);
// 堆的判空
int HeapSize(HP* php);

2.2 20250312_heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"20250312_heap.h"void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);if (php->a == NULL){perror("HeapInit::malloc fail!");return;}php->size = 0;php->capacity = 4;
}void swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//根据孩子位置，计算父亲位置while (child > 0)//child = 0,说明parent不存在了,已经到堆顶了{if (a[child] > a[parent]) //当孩子大小大于父亲大小的时候就交换{swap(&a[child], &a[parent]);//因为其他地方也要用到交换，封装了一个交换函数child = parent; //现在把父亲的值给孩子。parent = (child - 1) / 2;//继续计算现在节点的父亲结点，}else//孩子<=父亲 没必要往上走，直接break就行。		{break;}}
}void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容判断if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);if (tmp == NULL){perror("HeapPush::realloc fail!");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;	//在数组尾巴插入数据php->size++;//给size++//封装一个调整函数，在函数内判断是否进行交换，交换就直接换。AdjustUp(php->a,php->size-1);
}void AdjustDown(HPDataType* a, int n ,int parent)
{int child = parent*2+1;//根据父亲位置，计算孩子位置while (child <n)//走到没有孩子的时候，结束，{// 选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child])//必须把child+1<n放前面，否则后面a[child+1]就越界了！{++child;}//交换if (a[child] > a[parent]){swap(&a[child],&a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP * php)
{assert(php);assert(!HeapEmpty(php));//删除数据//（1）交换堆顶和最后一个数据 直接删掉。swap(&php->a[0], &php->a[php->size-1]);php->size--;//新的堆顶元素向下调整AdjustDown(php->a, php->size,0);
}HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}

2.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"20250312_heap.h"int main()
{HP hp;HeapInit(&hp);HeapPush(&hp, 1);HeapPush(&hp, 24);HeapPush(&hp, 7);HeapPush(&hp, 9);HeapPush(&hp, 4);HeapPop(&hp);HeapPop(&hp);return 0;
}

http://www.ppmy.cn/server/175796.html

相关文章

Centos 7 在线磁盘扩容

Centos 7 在线磁盘扩容

lsblk df -Th 查看磁盘信息 df -Th 1 查看物理卷 pvs 或者 pvdisplay 或者 pvscan [rootoracledb Thu Mar 13 13:53:44 /]# pvs PV VG Fmt Attr PSize PFree /dev/sda3 centos lvm2 a-- <237.28g 0 /dev/sdb1 centos lvm2 a-- <1…
阅读更多...
经历过的IDEA+Maven+JDK一些困惑

经历过的IDEA+Maven+JDK一些困惑

注意事项&#xff1a;由于使用过程中是IDEA绑定好另外2个工具&#xff0c;所以报错统一都显示在控制台&#xff0c;但要思考和分辨到底是IDEA本身问题导致的报错&#xff0c;还是maven导致的 标准配置 maven Java Compiler Structure 编辑期 定义&#xff1a;指的是从open pr…
阅读更多...
LOWORD(wParam) 与 HIWORD(wParam) 详解

LOWORD(wParam) 与 HIWORD(wParam) 详解

书籍&#xff1a;《Visual C 2017从入门到精通》的2.3.8 Win32控件编程 环境&#xff1a;visual studio 2022 内容&#xff1a;【例2.29】模拟对话框 说明&#xff1a;以下内容大部分来自腾讯元宝。 ​1. 基本概念与作用 LOWORD 和 HIWORD 是 Windows API 中用于分解 32 位…
阅读更多...
从零开始的 Kafka 学习（三）| 创建主题

从零开始的 Kafka 学习（三）| 创建主题

1. 创建主题 Topic 主题是 Kafka 中消息的逻辑分类&#xff0c;但是这个分类不应该是固定的&#xff0c;而是应该由外部的业务场景进行定义&#xff08;注意&#xff1a;Kafka 中其实是有两个固定的&#xff0c;用于记录消费者偏移量和事务处理的主题&#xff09;&#xff0c;…
阅读更多...
PyTorch 深度学习实战（15）：Twin Delayed DDPG (TD3) 算法

PyTorch 深度学习实战（15）：Twin Delayed DDPG (TD3) 算法

在上一篇文章中&#xff0c;我们介绍了 Deep Deterministic Policy Gradient (DDPG) 算法&#xff0c;并使用它解决了 Pendulum 问题。本文将深入探讨 Twin Delayed DDPG (TD3) 算法&#xff0c;这是一种改进的 DDPG 算法&#xff0c;能够有效解决 DDPG 中的过估计问题。我们将…
阅读更多...
vue3:八、登录界面实现-忘记密码

vue3:八、登录界面实现-忘记密码

该文章实现登录界面的忘记密码功能&#xff0c;点击忘记密码文本&#xff0c;打开dialog对话框 一、页面效果 加入忘记密码&#xff0c;在记住密码的同一行中&#xff0c;实现flex-between 二、对话框实现 1、新建组件页面 2、引入dialog组件到组件页面 参考路径 Dialog 对…
阅读更多...
《Operating System Concepts》阅读笔记：p272-p285

《Operating System Concepts》阅读笔记：p272-p285

《Operating System Concepts》学习第 27 天&#xff0c;p272-p285 总结&#xff0c;总计 14 页。 一、技术总结 1.semaphore A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() an…
阅读更多...
【人工智能】人工智能安全（AI Security）

【人工智能】人工智能安全（AI Security）

人工智能安全&#xff08;AI Security&#xff09; 是指保障人工智能系统免受各种攻击、滥用和错误操作的措施与技术。随着人工智能的广泛应用&#xff0c;AI的安全性问题变得越来越重要。AI安全不仅关注系统本身的稳定性与安全性&#xff0c;还涉及到如何确保AI的决策和行为是…
阅读更多...
最新文章

Copyright @ 2022~2023