【数据结构】二叉树的顺序结构实现及时间复杂度计算(二)

目录

一,二叉树的顺序结构实现

        1,二叉树的顺序结构

        2,堆的概念及结构

        3,堆的接口实现

1,堆的创建

2,接口函数

3,初始化

4,销毁

5,是否增容

6,交换数据

7,堆向上调整算法

8,插入数据

9,删除数据

10,堆向下调整算法

11,打印数据

12,取堆顶元素

13,判空

14,数据个数

        4,源代码

1,Heap.h

2,Heap.c

二,建堆的时间复杂度

        1,堆的创建

1,向上调整建堆法:

2,向下调整建堆法

        2,向上调整建堆的时间复杂度

        3,向下调整建堆的时间复杂度

三,堆的应用

        1,堆排序

1,建堆

2,利用堆交换删除思想来进行排序

        2,TOP-K问题


一,二叉树的顺序结构实现

        1,二叉树的顺序结构

普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储

二叉树的顺序储存结构就是用一堆数组储存二叉树中的结点,并且结点的储存位置,也就是数组的下标要能体现结点之间的逻辑关系,比如双亲与孩子的关系,左右兄弟的关系等;

        2,堆的概念及结构

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段;

如果有一个关键码的集合K = {k0 ,k1 ,k2 ,…,kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足父亲结点的值大于等于或者小于等于子孙结点的值,则称为大堆(或小堆)

将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆;

堆的性质:

1,堆中某个结点的值总是不大于或不小于其父结点的值;

2,堆总是一棵完全二叉树

        3,堆的接口实现

1,堆的创建

//堆(二叉树)的基本顺序结构
//动态顺序表
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

首先创建一个结构体表示顺序表,这里我们将数据类型重命名为HPDataType,便于我们后续对顺序表数据类型的修改;

a为类型指针代表一维数组

size为有效数据个数,capacity储存数据的最大容量值

2,接口函数

// 小根堆
// 堆初始化
void HPInit(HP* php);
// 销毁
void HPDestroy(HP* php);
// 是否增容
void HPCapacity(HP* php);
// 交换数据
void swap(HPDataType* x, HPDataType* y);
// 向上调整
void AdJustUp(HPDataType* a, int size);
// 插入数据
void HPPush(HP* php, HPDataType x);
// 向下调整
void AdJustDown(HPDataType* a, int size, int parent);
// 删除数据
void HPPop(HP* php);
// 打印数据
void HPPrint(HP* php);
// 取堆顶元素
HPDataType HPTop(HP* php);
// 判空
int HeapEmpty(HP* php);
// 数据个数
int HPSize(HP* php);

这里我们实现小根堆大小根堆的实现原理都一样;

以上是要实现的接口函数;

3,初始化

	//定义HP hp;//初始化HPInit(&hp);
// 堆的初始化
void HPInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);php->size = 0;php->capacity = 4;
}

首先要进行断言php不能为空,如果php为空则下面对php解引用就会报错;

刚开始先给 a 申请4个HPDataType大小的空间,这个自己可以任意修改,然后对sizecapacity进行赋值;

易错点:给指针a申请的是HPDataType大小的空间而不是HP大小的空间,这里由于学习过链表的缘故就容易搞混淆;

4,销毁

// 堆的销毁
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

然后就是销毁顺序表,直接用 free 释放掉 a 即可,再置为空指针,再重置 size 和 capacity ;

5,是否增容

//是否增容
void HPCapacity(HP* php)
{assert(php);if (php->size == php->capacity){php->a = (HPDataType*)realloc(php->a,sizeof(HPDataType)*(php->capacity * 2));if (php->a == NULL){perror("realloc");exit(-1);}php->capacity *= 2;}
}

像后面如果进行数据插入的话,就需要检查空间是否需要增容了,也很好判断,当size等于capacity时就需要增容了,我们这里是选择直接扩容一倍;

然后再更新一下capacity的值就行了;

6,交换数据

//交换数据
void swap(HPDataType* x, HPDataType* y)
{assert(x&&y);HPDataType z = *x;*x = *y;*y = z;
}

老样子先对指针xy进行断言,然后定义z完成xy的值交换,交换数据后续会使用到;

7,堆向上调整算法

//向上调整
void AdJustUp(HPDataType* a,int size)
{assert(a);int child = size-1;while (child>0){int parent = (child - 1) / 2;//孩子与父亲比较值if (a[child] < a[parent]){//交换swap(&a[child], &a[parent]);child = parent;}else{break;}}
}

先断言,当向堆中插入数据数据需要与父亲结点进行比较调整

我们传入指针a,数据个数sizesize用来确定插入数据的下标

然后建立循环遍历,父亲(parent)结点的下标为孩子(child)结点的下标减一除以二:

parent=(child -1)/ 2

a[child]的值小于a[parent]的值则进行交换,此时parent的身份转变为child继续向上调整,当child小于等于0,此时已到顶点无需再进行调整,退出循环;

8,插入数据

//插入数据
void HPPush(HP* php, HPDataType x)
{assert(php);//是否增容HPCapacity(php);php->a[php->size] = x;php->size++;//向上调整AdJustUp(php->a, php->size);
}

首先判断是否需要增容,此时size的值就是末尾的数的下标加一

直接对其下标进行赋值,再让size加一

然后就需要将新数据向上调整,相当于更新维护堆结构

9,删除数据

//删除数据
void HPPop(HP* php)
{assert(php);assert(php->size > 0);//交换数据值swap(&php->a[php->size - 1], &php->a[0]);php->size--;//向下调整AdJustDown(php->a, php->size,0);
}

删除堆顶数据;

我们要删除数据不能直接删除否则会破坏堆结构,重新调整代价太大(时间复杂度太大);

我们可以将插入的数据与堆顶的数据进行交换,然后再让size--相当于删除了堆顶数据,然后再让堆顶的数据向下进行调整,以此来更新维护堆结构;

10,堆向下调整算法

//向下调整
void AdJustDown(HPDataType* a, int size,int parent)
{assert(a);int child = parent * 2 + 1;while (child<size){//左孩子与右孩子比较值if (child+1<size && a[child]>a[child + 1]){child++;}//孩子与父亲比较值if (a[child] < a[parent]){//交换swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

孩子(child) 的下标等于父亲(parent) 下标×2+1:child=parent*2+1

建立循环遍历数组,先令左孩子为要与父亲比较的孩子,然后如果右孩子存在再让左孩子与右孩子进行比较,选出值小的孩子;

然后让孩子与父亲进行比较,如果孩子小于父亲则进行值的交换,此时孩子的身份变成父亲,继续循环;

当孩子的值大于等于size时循环结束,或者当孩子大于等于父亲则跳出循环;

11,打印数据

//打印数据
void HPPrint(HP* php)
{assert(php);int i = 0;for (i = 0; i < php->size; i++){printf("%d ", php->a[i]);}
}

堆是个顺序表;

size是数据个数,然后进行遍历打印即可;

12,取堆顶元素

//取堆顶元素
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

直接返回堆顶的数据即可

13,判空

//判空
int HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}

直接返回 size是否等于0的判断结果即可,如size等于0则为真,不等于0则为假;

14,数据个数

//数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}

直接返回size即可;

        

        4,源代码

1,Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>//堆(二叉树)的基本顺序结构
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;// 小根堆// 堆初始化
void HPInit(HP* php);
// 销毁
void HPDestroy(HP* php);
// 是否增容
void HPCapacity(HP* php);
// 交换数据
void swap(HPDataType* x, HPDataType* y);
// 向上调整
void AdJustUp(HPDataType* a, int size);
// 插入数据
void HPPush(HP* php, HPDataType x);
// 向下调整
void AdJustDown(HPDataType* a, int size, int parent);
// 删除数据
void HPPop(HP* php);
// 打印数据
void HPPrint(HP* php);
// 取堆顶元素
HPDataType HPTop(HP* php);
// 判空
int HeapEmpty(HP* php);
// 数据个数
int HPSize(HP* php);

2,Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"//堆初始化
void HPInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);php->size = 0;php->capacity = 4;
}
//销毁
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}
//交换数据
void swap(HPDataType* x, HPDataType* y)
{assert(x&&y);HPDataType z = *x;*x = *y;*y = z;
}
//向上调整
void AdJustUp(HPDataType* a,int size)
{assert(a);int child = size-1;while (child>0){int parent = (child - 1) / 2;if (a[child] < a[parent]){swap(&a[child], &a[parent]);child = parent;}else{break;}}
}
//是否增容
void HPCapacity(HP* php)
{assert(php);if (php->size == php->capacity){php->a = (HPDataType*)realloc(php->a,sizeof(HPDataType)*(php->capacity * 2));if (php->a == NULL){perror("realloc");exit(-1);}php->capacity *= 2;}
}
//插入数据
void HPPush(HP* php, HPDataType x)
{assert(php);//是否增容HPCapacity(php);php->a[php->size] = x;php->size++;AdJustUp(php->a, php->size);
}//向下调整
void AdJustDown(HPDataType* a, int size,int parent)
{assert(a);int child = parent * 2 + 1;while (child<size){//左孩子与右孩子比较值if (child+1<size && a[child]>a[child + 1]){child++;}//孩子与父亲比较值if (a[child] < a[parent]){//交换swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//删除数据
void HPPop(HP* php)
{assert(php);assert(php->size > 0);swap(&php->a[php->size - 1], &php->a[0]);php->size--;AdJustDown(php->a, php->size,0);
}
//打印数据
void HPPrint(HP* php)
{assert(php);int i = 0;for (i = 0; i < php->size; i++){printf("%d ", php->a[i]);}
}
//取堆顶元素
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//判空
int HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}//数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}

二,建堆的时间复杂度

        1,堆的创建

下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆根节点左右子树不是堆,我们怎么调整呢?

这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆

int a[] = { 7,8,3,5,1,9,5,4 };
HPSort(a, sizeof(a) / sizeof(a[0]));

1,向上调整建堆法:

//建堆--向上调整建堆 
int num = n;
for (int i = 1; i <= num; i++)
{//向上调整AdJustUp(a,i);
}

直接一直循环插入数据即可;

2,向下调整建堆法

//建堆--向下调整建堆  O(N)
int num = n;
for (int i = (num - 1 - 1) / 2;i >= 0; i--)
{//向下调整AdJustDown(a,n,i);
}

需要先把根结点下面的子树都搞成堆,所以先从倒数的第一个非叶子节点的子树开始向下调整,然后循环遍历让结点逐渐缩减(逐渐往上走)向下调整,如图所示;

        2,向上调整建堆的时间复杂度

  F(h)=2^1*1+2^2*2+...+2^(h-2)*(h-2)+2^(h-1)*(h-1)

2*F(h)=2^2*1+2^3*2+...+2^(h-1)*(h-2)+2^h*(h-1)

两式错位相减:

F(h)= - 2^1-2^2-2^3-...-2^(h-2)-2^(h-1)+2^h*(h-1)

F(h)= - 2^h+2-2^h+2^h*h

F(h)=2^h(h-2)+2

假设树有N个结点:2^h-1=N      h=log(N+1)

F(N)=(N+1)*(log(N+1)-2) + 2 ≈ N*logN

所以用向上调整建堆的时间复杂度为O(N*logN);

        3,向下调整建堆的时间复杂度

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

则需要移动结点总的移动步数为:

T(n) = 2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+2^3*(h-4)+...+2^(h-3)*2+2^(h-2)*1

2*T(n)=2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+2^4*(h-4)+...+2^(h-2)*2+2^(h-1)*1

两式错位相减:

T(n)=1-h+2^1+2^2+2^3+2^4+...+2^(h-2)+2^(h-1)

T(n)=2^h-1-h

n=2^h-1  ==  h=log(n+1)

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

所以用向下调整建堆的时间复杂度为O(N);

由此可见,建堆的时间复杂度为O(N)!

三,堆的应用

        1,堆排序

1,建堆

升序:建大堆

降序:建小堆

2,利用堆交换删除思想来进行排序

int num = n;
while (num>1)
{//交换数据swap(&a[0], &a[num-1]);num--;//向下调整AdJustDown(a,num,0);
}

其实很简单,比如我们要整一个升序数组,有人会说建小堆,其实这是错的;

如果建小堆:堆顶的数不变,找次大的数要将堆顶以下的数全部重新排序,这不现实,所以pas;

建大堆:堆顶的数据与末尾的数据交换,然后令num--(将末尾的数隔离开),再将堆顶的数向下调整,然后循环遍历一直找次大的数,当num等于1时堆顶的数为最小值,此时的数组便是升序数组!

这就是堆的交换删除思想,这个循环的时间复杂度为O(N*logN)

        2,TOP-K问题

TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大

比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等

对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决;

正常思路:

把这个N建成大堆,PopK次,即可找出最大的前K

但是,当N非常大时,假设N时10亿,那就是10亿个整数,所需的空间太大了,不可取!

优化思路:

1,将前K个数建成小堆

2,后面将N-K个数依次与堆顶的数据进行比较,如比堆顶的数据大,则替换他为堆顶,然后向下调整

3,最后比较完了,这个小堆的值就是最大的前K个

第二阶段就到这里了,下面更新二叉树的链式结构的实现;

如有不足之处欢迎来补充交流!

完结。。。


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/125285.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【线性表】

好久没更新啦&#xff0c;来喽来喽~~~ 喏&#xff0c;看这个图&#xff0c;什么意思呢&#xff1f;先容大家思考思考...... 目录&#xff1a; 1.线性表的定义 2.线性表的抽象数据类型 3.线性表的顺序存储结构 &#xff08;1&#xff09;顺序存储定义 &#xff08;2&#x…

LeetCode 面试题 02.07. 链表相交

文章目录 一、题目二、C# 题解 一、题目 给你两个单链表的头节点 headA 和 headB&#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点&#xff0c;返回 null。 图示两个链表在节点 c1 开始相交&#xff1a;   题目数据 保证 整个链式结构中不存在环。…

Vue + Element UI 前端篇(九):接口格式定义

接口请求格式定义 前台显示需要后台数据&#xff0c;我们这里先把前后端交互接口定义好&#xff0c;没有后台的时候&#xff0c;也方便用mock模拟。 接口定义遵循几个规范&#xff1a; 1. 接口按功能模块划分。 系统登录&#xff1a;登录相关接口 用户管理&#xff1a;用户…

Windows无法删除分区怎么办?

我们知道Windows系统内置的磁盘管理工具是一个很实用的程序&#xff0c;可以帮助我们完成很多磁盘分区相关的基础操作&#xff0c;比如当我们想要删除硬盘上的某一个分区时&#xff0c;先想到的可能会是磁盘管理工具。但是当我们准备在磁盘管理工具中删除某个分区时&#xff0c…

ArcGIS Maps SDK for JS(二):MapView简介----创建2D地图

文章目录 1 AMD 引用 ArcGIS Maps SDK for JavaScript2 加载相应模块3 创建地图4 创建 2D 视图 view5 确定页面内容6 CSS 样式7 完整代码 本教程使用 AMD 模块&#xff0c;指导您如何在二维地图视图中创建一个简单的地图。 1 AMD 引用 ArcGIS Maps SDK for JavaScript 在 <…

【zookeeper】zookeeper日常运维

本文将分享一些zookeeper在日常使用中一些维护经验。 zookeeper清理快照 脚本或者命令清理 zookeeper长时间运行&#xff0c;快照逐渐增多可能造成服务器磁盘被占满的情况&#xff0c;但我们不能贸然用rm命令删除快照文件&#xff0c;如果直接删完会导致丢失好多数据&#x…

使用ppt和texlive生成eps图片(高清、可插入latex论文)

一、说明 写论文经常需要生成高清的图片插入到论文中&#xff0c;本文以ppt画图生成高质量的eps图片的实现来介绍具体操作方法。关于为什么要生成eps图片&#xff0c;一个是期刊要求&#xff08;也有不要求的&#xff09;&#xff0c;另一个是显示图像的质量高。 转化获得eps…

vue 页面加水印

首先创建一个waterMark.js文件&#xff0c;当然文件命名可自定义&#xff0c; use strictconst watermark {}/**** param {要设置的水印的内容} str* param {需要设置水印的容器} container*/ const setWatermark (str, container) > {const id 1.23452384164.123412415…

9.8day58 单调栈

739. 每日温度 - 力扣&#xff08;LeetCode&#xff09; 知识点&#xff1a;1.建栈 2.如果后面要加入的数小于栈顶元素就把数组的下标压进栈里 3.反之 就让该数于栈顶元素进行比较 如果该数大于栈顶元素&#xff08;while&#xff09; 就把栈顶元素下表对应的arr数组的值进行…

嵌入式Linux驱动开发(同步与互斥专题)(二)

一、自旋锁spinlock的实现 自旋锁&#xff0c;顾名思义&#xff1a;自己在原地打转&#xff0c;等待资源可用&#xff0c;一旦可用就上锁霸占它。 ① 原地打转的是CPU x&#xff0c;以后CPU y会解锁&#xff1a;这涉及多个CPU&#xff0c;适用于SMP系统&#xff1b; ② 对于单…

4.3.3.1 【MySQL】CHAR(M)列的存储格式

我们知道 Compact 行格式在 CHAR(M) 类型的列中存储数据的时候还挺麻烦&#xff0c;分变长字符集和定长字符集的情况&#xff0c;而在 Redundant 行格式中十分干脆&#xff0c;不管该列使用的字符集是啥&#xff0c;只要是使用 CHAR(M) 类型&#xff0c;占用的真实数据空间就是…

Java-HashMap中put()方法是如何实现的,内含详细流程图

文章目录 Java中的HashMap什么是HashMap&#xff1f;对比其他Map中put()方法HashMap中put()方法使用示例 HashMap中put()源码解析手绘流程图实现原理源码探究&#xff08;JDK 1.8&#xff09; 设计put()的意义总结 Java中的HashMap 什么是HashMap&#xff1f; HashMap是Java中…

2023国赛数学建模C题模型代码

C题代码全部都完成了&#xff0c;可以看文末名片 我们先看C题的一个背景 在生鲜商超中,蔬菜类商品保鲜期短,且品相会随销售时间增加而变差。商超需要根据历史销售和需求每天进行补货。由于蔬菜品种众多、产地不同,补货时间在凌晨,商家须在不明确具体单品和价格的情况下进行补…

好奇!为什么很少看到女项目经理?

最近被刚进公司的新人问到&#xff0c;在项目管理领域&#xff0c;为什么女性项目经理的数量相对较少。一时之间我也有些茫然&#xff0c;下了班总结一下&#xff0c;跟大家探讨探讨。 一、职业选择的局限性 其实大多数时候&#xff0c;出现和性别有关的问题时&#xff0c;都是…

mockjs+json-server模拟百万条数据

文章目录 前言场景前置操作安装axios或者Ajax&#xff08;作者用的是axios&#xff09;mock.js文件编辑编辑json-server文件夹添加百万条虚拟数据后言 前言 hello world 欢迎来到前端的世界 &#x1f61c;当前文章系列专栏&#xff1a;前端 &#x1f431;‍&#x1f453;博主在…

QT文件对话框,将标签内容保存至指定文件

一、主要步骤 首先&#xff0c;通过getSaveFileName过去想要保存的文件路径及文件名&#xff0c;其次&#xff0c;通过QFile类实例化一个文件对象&#xff0c;再读取文本框中的内容&#xff0c;最后将读取到的内容写入到文件中&#xff0c;最后关闭文件。 1.txt即为完成上述操作…

架构设计基础设施保障IaaS之网络

目录 1 DNS运用1.1 DNS功能作用1.2 DNS配置实践 2 DNS生产最佳实践方案2.1 全球加速功能2.2 不同运营商的加速方案2.3 全球业务高可用方案2.4 跨地域负载均衡 3 DNS域名劫持解决方案4 CDN剖析4.1 CDN原理4.2 缓存过期配置处理流程4.3 缓存配置规则 5 CDN运用6 CDN最佳实践方案6…

检索与毒害 —— 对抗人工智能供应链攻击

作者&#xff1a;DAVE ERICKSON 在这篇文章中&#xff0c;了解人工智能大语言模型的供应链漏洞&#xff0c;以及如何利用搜索引擎的人工智能检索技术来对抗人工智能的错误信息和故意篡改。 虽然对于人工智能研究人员来说可能是新鲜事&#xff0c;但供应链攻击对于网络安全世界…

入栏需看——学习记忆

记忆方法千千种&#xff0c;本栏意在梳理其中道道来&#xff0c;旦有小得&#xff0c;肥肠幸耶。从不同角度分析学习记忆。 逻辑篇 有逻辑 用思维导图 思维导图记忆有逻辑的文本/内容 理论 巧记书本结构–思维导图 模仿 HCIE-Cloud Computing LAB备考第一步&#xff1a…

解某麦数据请求参数analysis加密

意外发现一个可以查询app下载量得网站&#xff0c; 想筛选一下哪些下载量在1w-10w之间&#xff0c;大概需要5k个.。 感觉应该没啥加密&#xff0c;好把&#xff0c;是我小看了&#xff0c;有个参数是加密得&#xff0c;如图。 analysis 扣js开始&#xff0c; f12 去资源文件…