【数据结构初阶】二叉树--堆(顺序结构实现)

2024-09-01 22:28
文章标签 二叉树 实现 数据结构 初阶 结构 顺序

本文主要是介绍【数据结构初阶】二叉树--堆(顺序结构实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

hello！

目录

一、实现顺序结构二叉树

1.1  堆的概念和结构

1.2  堆及二叉树的性质

1.3  堆的实现

1.3.1  创建堆的结构

1.3.2  初始化和销毁

1.3.3  入堆+向上调整算法（创建一个小堆）

1.3.4  出堆+向下调整算法（小堆）

1.3.5  判空+取堆顶数据+堆中有效数据个数

二、顺序结构二叉树---源码

Heap.h

Heap.c

test.c

Relaxing Time！

—————————————  《星空物语》  —————————————

正文开始——

一、实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，分为大根堆（大堆）和小根堆（小堆），具有二叉树的特性的同时，还具备其他的特性。

1.1  堆的概念和结构

如果有一个关键码的集合K={k1，k2,，k3，...，k（n-1）}，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足：Ki <= K(2*i+1)（Ki >= K(2*i+1) 且 Ki >= K(2*i+2)），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 则无右孩子；

通俗点来讲，父结点i---> 左孩子：2i+1，右孩子：2i+2。

1.3  堆的实现

1.3.1  创建堆的结构

堆的底层结构是数组 

//创建堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;//堆中有效数据的个数int capacity;//堆的容量
}HP;

1.3.2  初始化和销毁

//初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}//销毁
void HPDestroy(HP* php)
{assert(php);if(php->arr){free(php->arr);php->arr = NULL;}php->size = php->capacity = 0;}

1.3.3  入堆+向上调整算法（创建一个小堆）

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

向上调整算法

  • 先将元素插入到堆的末尾，即最后一个子结点之后；
  • 插入之后如果堆的性质遭到破坏，将新插入结点顺着双亲结点往上调整到合适位置即可。 

【举例，向上调整算法】

思路：新插入的数据作为子结点（child），找到新插入数据的父结点（parent=（child-1）/ 2）（上面二叉树的性质），父结点和子结点进行比较，若父结点大于子结点，数据交换，不大于则不交换。再找新的父结点和子结点，循环条件是 child>0，child不需要等于0，child等于0时为根结点，根结点没有父结点不需要发生交换。

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否充足if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc file!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//此时空间已经充足//我们应该清楚地知道，size是x的下标，size在数组中指向x这个元素php->arr[php->size] = x;//向上调整算法AdjustUp(php->arr, php->size);php->size++;
}

1.3.4  出堆+向下调整算法（小堆）

堆的删除（出堆）

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

向下调整算法有一个前提：左右子树必须是一个堆，才能进行调整。

出堆

  • 将堆顶元素与堆中最后一个元素进行交换；
  • 删除堆中最后一个元素；
  • 将堆顶元素向下调整到满足堆特性为止。

 【向下调整算法】

思路：堆顶元素为父结点，找到左右孩子中最小的那个子结点与之比较，若父结点大于子结点，交换，不大于则不交换，不断找新的父结点和子结点，就这样循环，注意循环结束的条件。上代码，结合代码中的注释更好的理解。

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n){//找左右孩子中最小的//child + 1 < n , 保证不越界if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[parent] > arr[child]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//出堆
void HPPop(HP* php)
{assert(php && php->size);Swap(&php->arr[0], &php->arr[php->size-1]);php->size--;//删除掉最后一个数据(堆顶元素)//向下调整算法AdjustDown(php->arr, 0, php->size);}

1.3.5  判空+取堆顶数据+堆中有效数据个数

//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}//取堆顶数据
HPDataType HPTop(HP* php)
{assert(php && php->size);return php->arr[0];
}//堆中有效数据的个数
int HPSize(HP* php)
{assert(php);return php->size;
}

二、顺序结构二叉树---源码

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>//创建堆的结构
typedef int HPDataType;
typedef struct Heap
{int* arr;int size;//堆中有效数据个数int capacity;//堆的容量
}HP;//初始化
void HPInit(HP* php);//销毁
void HPDestroy(HP* php);//入堆
void HPPush(HP* php, HPDataType x);//出堆
void HPPop(HP* php);//判空
bool HPEmpty(HP* php);//取堆顶数据
HPDataType HPTop(HP* php);//堆中有效数据的个数
int HPSize(HP* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"//初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}//销毁
void HPDestroy(HP* php)
{assert(php);if (php->arr){free(php->arr);php->arr = NULL;}
}void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0)//不需要等于0，child等于0时为根结点，根结点没有父结点不需要发生交换{if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//入堆
void HPPush(HP* php,HPDataType x)
{assert(php);//判断空间是否充足if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc file!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//此时空间已经充足php->arr[php->size] = x;//向上调整算法AdjustUp(php->arr, php->size);php->size++;}//向下调整算法
void AdjustDown(HPDataType* 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[parent] > arr[child]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//出堆
void HPPop(HP* php)
{assert(php && php->size);Swap(&php->arr[0], &php->arr[php->size-1]);php->size--;//向下调整算法AdjustDown(php->arr, 0, php->size);}//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}//取堆顶数据
HPDataType HPTop(HP* php)
{assert(php && php->size);return php->arr[0];
}//堆中有效数据的个数
int HPSize(HP* php)
{assert(php);return php->size;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"void test01()
{HP hp;HPInit(&hp);int arr[] = { 1,3,5,7,4,10,8 };for (int i = 0; i < 7; i++){HPPush(&hp, arr[i]);}printf("堆中有效数据个数：%d\n", HPSize(&hp));while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);}int main()
{test01();return 0;
}

完——

Relaxing Time!

—————————————  《星空物语》  —————————————

星空物语（电视剧《一起来看流星雨》主题曲） - 张翰/朱梓骁/魏晨/俞灏明 - 单曲 - 网易云音乐

我是云边有个稻草人

期待与你的下一次相遇——

这篇关于【数据结构初阶】二叉树--堆(顺序结构实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1128219。

相关文章

MySQL索引的优化之LIKE模糊查询功能实现

MySQL索引的优化之LIKE模糊查询功能实现

《MySQL索引的优化之LIKE模糊查询功能实现》：本文主要介绍MySQL索引的优化之LIKE模糊查询功能实现,本文通过示例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一、前缀匹配优化二、后缀匹配优化三、中间匹配优化四、覆盖索引优化五、减少查询范围六、避免通配符开头七、使用外部搜索引擎八、分
阅读更多...
Python实现特殊字符判断并去掉非字母和数字的特殊字符

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa
阅读更多...
Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

《SpringBoot集成Quartz并使用Cron表达式实现定时任务》本篇文章介绍了如何在SpringBoot中集成Quartz进行定时任务调度,并通过Cron表达式控制任务... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启动 Sprin
阅读更多...
Android实现悬浮按钮功能

Android实现悬浮按钮功能

《Android实现悬浮按钮功能》在很多场景中,我们希望在应用或系统任意界面上都能看到一个小的“悬浮按钮”（FloatingButton）,用来快速启动工具、展示未读信息或快捷操作,所以本文给大家介绍... 目录一、项目概述二、相关技术知识三、实现思路四、整合代码4.1 Java 代码（MainActivi
阅读更多...
使用Python实现一个优雅的异步定时器

使用Python实现一个优雅的异步定时器

《使用Python实现一个优雅的异步定时器》在Python中实现定时器功能是一个常见需求,尤其是在需要周期性执行任务的场景下,本文给大家介绍了基于asyncio和threading模块,可扩展的异步定... 目录需求背景代码1. 单例事件循环的实现2. 事件循环的运行与关闭3. 定时器核心逻辑4. 启动与停
阅读更多...
基于Python实现读取嵌套压缩包下文件的方法

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件：使用with zipfile.ZipFil
阅读更多...
Python实现word文档内容智能提取以及合成

Python实现word文档内容智能提取以及合成

《Python实现word文档内容智能提取以及合成》这篇文章主要为大家详细介绍了如何使用Python实现从10个左右的docx文档中抽取内容,再调整语言风格后生成新的文档,感兴趣的小伙伴可以了解一下... 目录核心思路技术路径实现步骤阶段一：准备工作阶段二：内容提取 (python 脚本)阶段三：语言风格调
阅读更多...
C#实现将Excel表格转换为图片(JPG/ PNG)

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel
阅读更多...
基于Java实现回调监听工具类

基于Java实现回调监听工具类

《基于Java实现回调监听工具类》这篇文章主要为大家详细介绍了如何基于Java实现一个回调监听工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录监听接口类 Listenable实际用法打印结果首先，会用到 函数式接口 Consumer, 通过这个可以解耦回调方法，下面先写一个
阅读更多...
使用Java将DOCX文档解析为Markdown文档的代码实现

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown（MD）因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2