二叉树(二)

一、二叉树的顺序结构

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

二、堆的概念及结构

堆是完全二叉树,用数组存储。

大堆 :完全二叉树;任何一个父亲大于等于孩子(兄弟之间没有规定大小关系);根是最大的。

小堆 :完全二叉树;任何一个父亲小于等于孩子(兄弟之间没有规定大小关系);根是最小的。

 三、堆的实现

1.向下调整算法

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

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

2.堆的创建

给出一个数组,这个数组在逻辑上可以看成完全二叉树,但是还不是堆。从倒数第一个非叶子节点的子树开始,一直调整到根节点的树,就可以调整成堆。

int a[] = {1,5,3,8,7,6}; 

3. 调整建堆时间复杂度

堆是完全二叉树,满二叉树也是完全二叉树,这里使用满二叉树来证明(时间复杂度看的是近似值):

 4.堆的插入

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

5.堆的删除

若挪动覆盖删除堆顶数据,关系就乱了,兄弟变父子,叔侄变兄弟……

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

6.堆的代码实现 

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 HPInit(HP* php);
//销毁
void HPDestroy(HP* php);
//堆的插入
void HPPush(HP* php, HPDataType x);
//堆的删除
void HPPop(HP* php);
//取堆顶的数据
HPDataType HPTop(HP* php);
//堆的判空
bool HPEmpty(HP* php);

Heap.c文件:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
//初始化
void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}
//销毁
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0)//while (parent >= 0),这样写也能运行,但是这里存在bug://当parent=0时也会进入循环,parent=child=0,//虽然parent和child都等于0,但是a[child] < a[parent]不成立,//直接break,也能运行{if (a[child] < a[parent]){Swap(&a[child], &a[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 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{// 先假设左孩子小int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在,调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){++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[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}
//取栈顶数据
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}
//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

Test.c文件:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void TestHeap1()
{int a[] = { 4,2,8,1,5,6,9,7,3,23,55 };HP hp;HPInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);}int i = 0;while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}printf("\n");HPDestroy(&hp);
}
int main()
{TestHeap1();return 0;
}

四、堆排序

堆排序是利用堆的思想进行排序,分为两个步骤:

①建堆:升序建大堆,降序建小堆(若降序建大堆,关系全乱了)

②利用堆删除思想进行排序

建堆和堆删除都用到了向下调整,因此需要掌握向下调整,就可以完成堆排序。

#include<stdio.h>
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{// 先假设左孩子小int child = parent * 2 + 1;while (child < n){// 找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}
void TestHeap2()
{int a[] = { 4,2,8,1,5,6,7,9,3 };HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){printf("%d ", a[i]);}
}
int main()
{TestHeap2();return 0;
}

五、TOP-K问题

求数据中前K个最大或最小的元素,一般情况下数据量都比较大。

对于TOP-K问题,最简单最直接的方式就是排序,但是如果数据量非常大,排序就不可取了(数据不可能一下子全部加载到内存中)。

最佳的方式是用堆来解决:

①数据集合中前K个元素建堆:前K个最大的元素建小堆,前K个最小的元素建大堆——时间复杂度O(K);

②剩余数据依次和堆顶数据比较,不满足就替换堆顶数据(覆盖根位置,然后向下调整)——时间复杂度O(log K*(N-K))。

合计:O(N)

void CreateNDate()
{// 造数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void PrintTopK(int k)
{const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}// 建小堆for (int i = (k-1-1)/2; i >= 0; i--){AdjustDown(kminheap, k, i);}int val = 0;while (!feof(fout)){fscanf(fout, "%d", &val);if (val > kminheap[0]){kminheap[0] = val;AdjustDown(kminheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");
}

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

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

相关文章

Self-Supervised Learning(李宏毅老师系列)

自学参考&#xff1a; BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding BERT 论文逐段精读 视频课 课件资料 笔记 一、概述 自监督学习模型与芝麻街~ 参数量 ELMO&#xff1a;94MBERT&#xff1a;340MGPT-2&#xff1a;1542MMegatron&…

ubuntu查看CPU、内存、硬盘

1、查看CPU cat /proc/cpuinfo 我这台机器CPU是2核&#xff0c;所以这里是2核 或者使用如下命令也可以查看 lscpu 查看CPU使用率 top 2、查看内存 查看内存信息&#xff1a; free -h 查看内存使用情况&#xff1a; vmstat 3、硬盘 查看硬盘使用情况&#xff1a; df -…

uniapp 日常业务 随便写写 源码

现成的组件 直接用 <template><view style"margin: 10rpx;"><view class"tea-header"><text class"tea-title">礼尚往来</text><view class"tea-view-all"><text>查看全部</text>&l…

免费录屏软件之QQ

录屏太简单了 1、首先下载QQ 2、在随便打开个对话框&#xff0c;再操作1、2步骤即可 3、嫌打开对话框麻烦&#xff1f; 4、打开QQ后直接按下CtrlAltR即可录屏&#xff0c;连对话框都不用打开了&#xff0c;按完快捷键后效果如下&#xff1a; 5、点击右下角开始录屏即可

Electron:摄像头录制和屏幕录制

摄像头录制 main.js const { app, BrowserWindow} require(electron)let mainWin null const createWindow () > {mainWin new BrowserWindow({width: 800,height: 600,title: 自定义菜单,webPreferences: {// 允许渲染进程使用nodejsnodeIntegration: true,// 允许渲…

idea付费插件激活

以下idea付费插件均可激活 获取链接&#xff1a;https://web.52shizhan.cn

【Qt开发】QtCharts图表 在ui上添加QChartView控件并进行绘图配置

【Qt开发】QtCharts图表 在ui上添加QChartView控件并进行绘图配置 文章目录 控件安装和模块导入在ui上添加QChartView控件QChartView图表配置附录&#xff1a;C语言到C的入门知识点&#xff08;主要适用于C语言精通到Qt的C开发入门&#xff09;C语言与C的不同C中写C语言代码C语…

Datawhale X 魔搭 AI夏令营 Task1 从零入门AI生图原理实践笔记

赛题内容 参赛者需在可图Kolors模型的基础上训练LoRA模型&#xff0c;生成无限风格&#xff0c;如水墨画风格、水彩风格、赛博朋克风格、日漫风格… 基于LoRA模型生成8张图片组成连贯故事&#xff0c;故事内容可自定义&#xff1b;基于8图故事&#xff0c;评估LoRA风格的美感度…

基于 Android studio 实现停车场管理系统--原创

目录 一、项目演示 二、开发环境 三、项目页面 四、项目详情 五、项目完整源码 一、项目演示 二、开发环境 三、项目详情 1.启动页 这段代码是一个简单的Android应用程序启动活动&#xff08;Activity&#xff09;&#xff0c;具体功能如下&#xff1a; 1. **延迟进入登…

【OpenCV】window 下 VS Code 配置OpenCV

文章目录 前言直接使用OpenCV 编译好的库自己编译OpenCVVS Code 安装MinGW下载下载Cmake编译OpenCV VS Code 运行cv程序VSCode配置运行CV程序 参考文章 前言 在网上找了些资料&#xff0c;大致得出VS Code开发OpenCV的环境配置流程&#xff0c;如下 安装VS Code安装MinGW安装…

【三维重建】Pixel-GS:三维高斯泼溅的像素感知的梯度密度控制(去除浮点,提升精度)

项目&#xff1a;https://pixelgs.github.io/ 标题&#xff1a;Pixel-GS: Density Control with Pixel-aware Gradient for 3D Gaussian Splatting 来源&#xff1a;香港大学&#xff1b;腾讯AI Lab 文章目录 摘要一、前言二、相关工作1.新视图合成2.基于点的辐射场3.Floater 的…

论文写作新神器!10款可以写论文的人工智能软件

在当今快速发展的数字时代&#xff0c;人工智能&#xff08;AI&#xff09;技术已经渗透到各个领域&#xff0c;包括学术研究和论文写作。为了帮助学者和学生提高写作效率和质量&#xff0c;市场上涌现了许多优秀的AI写作工具。本文将详细介绍10款可以写论文的人工智能软件&…

图像文本擦除无痕迹!复旦提出EAFormer:最新场景文本分割新SOTA!(ECCV`24)

文章链接&#xff1a;https://arxiv.org/pdf/2407.17020 git链接&#xff1a;https://hyangyu.github.io/EAFormer/ 亮点直击 为了在文本边缘区域实现更好的分割性能&#xff0c;本文提出了边缘感知Transformer&#xff08;EAFormer&#xff09;&#xff0c;该方法明确预测文…

CPU飙升 怎么定位问题

传统的方法 【top】 查看所有进程占系统CPU的排序&#xff0c;定位是哪个进程搞的鬼。PID那一列就是进程号。 【top -Hp pid】 定位进程中使用 CPU 最高的线程tid 【printf ‘0x%x’ tid】 线程 tid 转化 16 进制,例如printf ‘0x%x’ 11882 得到16进制的 0x2e6a 【jstack…

PX4-Autopolite linux环境下源码编译中遇到的一些问题及相应解决办法

最近在做一个PX4飞控移植的项目&#xff0c;第一次接触到PX4源码&#xff0c;真的是感觉编译起来非常的麻烦&#xff0c;下面我将介绍几个新手比较容易踩坑的点。 &#xff08;我都踩了ㄒ-ㄒ&#xff09; 1.PX4源码要用git clone 从github上克隆来&#xff0c;千万不要直接在g…

java SE--集合

1.Collection接口 Collection接口是List&#xff0c;Set&#xff0c;Queue接口的父接口&#xff0c;里面提供了子类的常用方法&#xff1b; List储存的是可以重复的&#xff0c;有序的数据&#xff0c;子类是arrayList&#xff08;数组结构&#xff09;和linkedList&#xff…

Mapreduce_Distinct数据去重

MapReduce中数据去重 输入如下的数据&#xff0c;统计其中的地址信息&#xff0c;并对输出的地址信息进行去重 实现方法&#xff1a;Map阶段输出的信息K2为想要去重的内容&#xff0c;利用Reduce阶段的聚合特点&#xff0c;对K2进行聚合&#xff0c;去重。在两阶段中&#xff…

24/8/15算法笔记 强化学习贪婪算法,UCB,汤普森算法

以老虎机为例介绍各算法 import numpy as np#每个老虎机的中奖概率&#xff0c;0-1之间均匀分布 probs np.random.uniform(size10)#生成一个数组&#xff0c;其中的元素是从均匀分布&#xff08;也称为矩形分布&#xff09;中随机抽取的。均匀分布意味着每个数出现的概率是相…

微服务架构的未来发展趋势

文章目录 摘要引言当前发展趋势ServerlessService MeshAIOps 未来可能出现的挑战代码示例微服务架构示例 QA环节小结未来展望参考资料 摘要 微服务架构在软件开发中已经成为主流&#xff0c;但随着市场需求和技术环境的快速变化&#xff0c;微服务架构也在不断演进。本文将分析…

如何为 Nextcloud 配置自动数据库备份 - 应用程序

自动数据库备份模块简化了生成数据库计划备份的过程。这些备份可以存储在各种位置&#xff0c;包括本地驱动器、FTP 服务器、SFTP 服务器、Dropbox、Google Drive、OneDrive、NextCloud 和 Amazon S3 云存储。用户还可以选择启用自动删除过期备份的功能。此外&#xff0c;用户可…