建筑网站汇总,微信开发平台开发,做二手手机的网站有哪些,做电视的视频网站吗文章目录
前言
一、树
(一)、概念
1、树的定义
(二)、树的定义
1、树为什么是递归定义的#xff1f;
2、如何定义树(如何表达一棵树)
解决方案一#xff1a;假设我们得知该树的度
解决方案二#xff1a;顺序表
解决方案三#xff1a;左孩子右兄弟表示法
二、二叉…文章目录
前言
一、树
(一)、概念
1、树的定义
(二)、树的定义
1、树为什么是递归定义的
2、如何定义树(如何表达一棵树)
解决方案一假设我们得知该树的度
解决方案二顺序表
解决方案三左孩子右兄弟表示法
二、二叉树
(一)、概念
(二)、特殊二叉树
1、斜树
2、满二叉树
3、完全二叉树
(三)、现实中的二叉树
(四)、二叉树的性质
(五)、二叉树的存储结构
1、顺序存储结构
2、链式存储结构
三、堆
(一)、堆的概念
1、堆的定义
2、堆的性质
3、堆的特点
(二)、堆类型的声明
(三)、堆的实现
1、Heap.h 的实现
2、Heap.c 的实现
1、初始化
2、销毁
3、交换
4、向上调整
5、push
6、向下调整
7、pop
8、获取堆顶数据
9、判空
(四)、堆排序
1、建堆算法
方法一利用向上调整建堆
方法二利用向下调整建堆
2、堆排序
(五)、TOP-K 问题
解决方案一
解决方案二
总结 前言
路漫漫其修远兮吾将上下而求索 一、树
(一)、概念
1、树的定义 在之前学习的顺序表、链表、栈、队列均是一对一的线性结构(此线性为逻辑上的”线性“)而非线性结构的特点是复杂生活中当然不仅仅只是一对一的问题面对一对多的问题我们又该如何解决呢利用一对多的数据结构此处所要讲述的”树“便是一对多的数据结构 树是一种非线性的数据结构它是由 n (n0) 个有限结点组成的具有层次关系的集合将此结构叫做树的原因是因为此结构像一棵倒挂的树即其根在上而叶朝下
当n 0 时称此树为空树
在任意一棵非空树中(如下图所示)
1、有且只有一个特定的节点称为根(Root)结点根节点没有前驱节点2、当n1 时其余节点可以分为m(m0)个不相交的有限集T1、T2...Tm,其中一个集合本身又是一棵树并且称为根节点的子树(SubTree),每棵树的根节点可以有0个或者多个后继3、树是递归定义的 树为什么是递归定义的
请继续往下看下文中会有解释 树的定义中运用到了树的概念下图中的子树T1与子树T2 为上图根节点A的子树当然D、H组成的左子树与E组成的右子树又为根节点B的子树F 组成的右子树与G、I组成的右子树又作为根节点C的子树 注树形结构中子树之间不能有交集否则就不叫作树形结构(子树之间有交集叫做”图“)如下图所示 树形结构的特点
1、子树不相交2、除了根节点之外(根节点没有父节点)。每个结点有且有且只有一个父节点3、一棵N个节点的树有N-1条边
2、树的相关概念 节点的度一个节点含有的子树(孩子)个数称为该节点的度如上图节点A有三个子树故而A的度为3叶节点(终端节点)度为0的节点称为叶节点(没有子节点的节点)如上图中节点J、F、M、L、H、I为叶节点分支节点(非终端节点)度不为0的节点如上图B、C、D、E、G、K 为非终端节点父节点(双亲节点)若一个节点中包含子节点那么此节点便会被称为其子节点的父节点如上图节点A为节点B的父节点子节点(孩子节点)一个节点含有子树的根节点称为该节点的子节点如上图节点B是节点A的子节点兄弟节点: 具有相同父节点的节点称为兄弟节点如上图节点B、C、D称为兄弟节点树的度一棵树中节点中最大的度为该树的度如上图因为在所有节点中最大的度为节点A的3 故而该树的度为3节点的层次从根开始定义根为第一层根的子节点为第二层……以此类推下去(有些地方从第0层开始计算树的层数)树的高度或深度树中节点的最大层次如上图树的高度为5堂兄弟节点双亲在同一层的节点互为堂兄弟如上图节点E、J、H 互为堂兄弟节点节点的祖先: 从根节点到该节点所经历分支上的所有节点如上图A是所有节点的祖先节点J的祖先有A、B、E子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点均为A的子孙、节点B的子孙有E、F、J森林由m(m0) 棵不相交的树的集合合称为森林(即多棵树便称为森林) 注 在树的这部分利用树的相关概念(树、叶、分支) 以及人类亲缘关系进行命名一棵树是由叶节点(终端节点) 与 分支节点(非终端节点) 构成的 节点层次的概念如何区分
看你如何分着走可以从第0层开始也可以从第一层开始一般情况下从第1层开始因为树还有空树的概念这样的话空树便为第0层而若从第0层开始那么空树只能当作 -1层有点奇怪但是这样的表达没有问题
可能你会联想到数组的下标为什么是从0开始的而不是从1开始
数组的下标从0开始是被逼无奈的众所周知数组名表示首元素地址倘若此处有一个数组a 那么a[i] *(ai) ; 基于这个特点只有数组的下标从0开始才能满足此表达式-- a[0] *a ;
树的高度或深度-- 最大层次的概念 树的高度或者深度与其从第一层开始还是从第0层开始有关如若一棵树有6层并且其层次从第一层开始的那么该树的高度(深度)便为6而如若该树从第0层开始那么该树的高度便为5 此处并没有特别严格的概念来定义的高度(深度)由于一般情况下我们树的层次是从第一层开始的所以可以将树的高度当作其层数但是不要忘记树的高度的核心 —— 最大层次 (二)、树的定义
1、树为什么是递归定义的
任何一棵树均是由两部分组成的根节点 与 子树(即任何一棵树均包含根和N棵子树其中N大于等于0);
树是由根节点与子树构成而子树又是由根节点与子树构成子树又是由根节点与子树构成……故而说树是由递归构成的
如何理解递归?
递归的 ”核心“ 思想大事化小递归大问题可以拆分为小问题小问题可以拆解称更小的问题……直到这个问题被拆成不可以再拆解的问题才会停止而这些问题是相似的
回顾之前在C语言阶段学习的递归递归有两个条件 递归又称为”分治“即分而治之(将大问题化为小问题)
用图像来理解 由上图可知A这棵树由根节点A、子树B、子树C、子树D构成而子树B又由根节点B、子树E与子树F构成子树E由根节点E、子树J构成子树F由根节点F构成…… 从上图中可以清楚地看见一棵树由一个根节点与N个子树构成(N0) 而一个子树又由一个根节点与N个子树构成(N0)……当这棵树只有一个根节点的时候便不再分下去。
2、如何定义树(如何表达一棵树) 在前面的学习在定义单链表的结点时由于单链表的结点需要一个数值域来存放数据一个指针域来存放下一个结点的地址所以在定义单链表结点类型的时候定义一个数值域与指针域在双链表中需要一个数值域来存放数据两个指针域分别指向前一个结点与后一个结点故而在定义双链表结点类型的时候会定义一个数值域与两个指针域 而树是由根节点与子树(孩子)构成一棵树只有一个根节点这是显而易见的但由于并不知道有多少子节点定义树的时候究竟要定义多少个孩子就是一个问题
解决方案一假设我们得知该树的度
利用树的度建立一个指针数组在将此指针数组与数据封装在一个结构体中如下图所示 注如果此处的N很大那么此结构是存在空间浪费的
解决方案二顺序表
(在未知数的度的情况下)使用顺序表来存放子节点的地址
方案一相当于使用的是静态的数组来存放子节点的地址而方案二相当于是动态的数组来存放子节点的地址
此处使用顺序表本质上也是在使用数组只不过相较于方案一此处的数组中存放子节点地址的空间是动态开辟的这种方法不会浪费空间并且很直观但是不好控制、访问
解决方案三左孩子右兄弟表示法
就定义两个指针(leftChild、rightBrother)不在乎有多少个孩子定义如下 左孩子右兄弟表示法究竟特点在何处
让孩子去链接孩子兄弟去链接兄弟
如下图所示 如上图所示无论一个结点会有多少个孩子leftChild 均会指向其最左边的孩子剩余的孩子右rightBrother (亲兄弟)解决 二、二叉树
(一)、概念
二叉树(Binary Tree) 是n (n0) 个结点的有限集合该集合或者为空集(即空二叉树)或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树构成如下图 注 1、二叉树中节点的子节点个数小于等于2二叉树的度最大为2 2、二叉树中的子树存在左右之分次序不能颠倒故而二叉树又称为有序树 3、即使树中的节点只有一棵树也是需要区分此数为左子树还是右子树 二叉树的均为以下的二叉树复合而成 即二叉树的五种基本形态 1、空二叉树 2、只有一个根节点 3、根节点只有左子树 4、根节点只有右子树 5、根节点既有左子树又有右子树 (二)、特殊二叉树
1、斜树
顾名思义斜树就是斜着的树(二叉树只有左右之分故而可向左斜也可向右斜)
左斜树所有节点都只有左子树的二叉树右斜树所有节点均只有右子树的二叉树
斜树的特点每一层均只有一个节点节点的个数与其树的高度(深度)相同(从第一层开始算)如下图 2、满二叉树
在一棵二叉树中如果所有分支节点均存在左子树与右子树并且所有的叶节点均在同一层这样的二叉树便称为满二叉树换句话说此树的每一层均达到最大值倘若此树的层次为 k ,那么该树的总节点个数为 2^k-1 。如下图 满二叉树的特点 1、叶节点只能出现在最下面的一层 2、非叶节点的度一定为2 3、在同样高度(深度) 的二叉树中满二叉树的节点个数最多叶节点最多 3、完全二叉树
对一棵有n个节点的二叉树按层序进行编号如果编号为i (1 i n)的节点与同样深度的满二叉树中编号为 i 的节点在二叉树中的位置完全相同那么此二叉树便称为完全二叉树
换句话说完全二叉树如果有k 层其(k-1) 层均是满的最后一层即第k层不是满的但节点从左向右是连续的(中间没有空节点)
注满二叉树是一种特殊的完全二叉树 注完全二叉树的所有节点与其同深度的满二叉树他们按层序编号相同的节点是一一对应的关系
按层序编号例如上图中的左边的图中其每一层的编号均是连续的故而左图中的树为完全二叉树而右图中最后一层的编号并不是连续的编号10与11 空挡了故而该树并不是完全二叉树 完全二叉树的特点(在头脑中过一遍完全二叉树的图形即可无需记忆) 1、叶节点只能出现在最下面的两层 2、最后一层的叶节点一定会集中在左边连续位置上 3、倒数第二层如果有叶节点一定在右部连续的位置上 4、如果一个节点的度为1那么该节点只有左孩子即不会存在有右孩子的情况 5、同样节点数的二叉树中完全二叉树的深度最小 (三)、现实中的二叉树 (四)、二叉树的性质
性质一在二叉树的第 h 层最多有 2^(h-1) 个节点h1 即从第一层开始数
性质二深度为 h 的二叉树至多有 2^h -1 个节点 ,h1 即从第一层开始数;
注最多就是参考的满二叉树
(五)、二叉树的存储结构
二叉树的实现可以选择两种结构 1、数组 2、链表
即顺序存储结构与链式存储结构
1、顺序存储结构
二叉树的顺序存储结构就是使用一维数组存储二叉树中的节点并且数组的下标(节点的存储位置)要能够体现节点之间的存储逻辑
一般数组只适合用来存储完全二叉树因为完全二叉树中的节点均是连续存放的不会浪费空间在现实中只用使用堆才会用数组来存储节点因为堆的逻辑结构为完全二叉树二叉树的顺序存储在物理上是一个数组在逻辑上是一棵二叉树
注
1、满二叉树是一种特殊的完全二叉树
2、逻辑结构是想象出来的物理结构是真实存在的存储结构 为什么完全二叉树适合用数组来存放 1、存储简单不会浪费空间(完全二叉树的节点均是连续的) 2、可以利用下标来计算父子节点 从上图中分析我们可以得知假设父节点的下标为 i 如果此父节点有两个孩子那么其左孩子的下标为 2*i1 ,右孩子的下标为 2*i2 ; 同理反过来假设孩子的下标为 j ,如果此孩子为左孩子那么其父节点的下标为(j-1)/2 ; 而若此孩子为右孩子那么其父节点的下标为 : (j-2)/2 ; 计算机中的 / 会去除除法中的余数而只保留整数 假设父节点的下标为i ,那么左孩子的下标为 2*i1 , 其中1小于2那么当2*i-1 除以2 的时候结果就是 i ,当然将这个1减去计算结果也为i因为1小于2不会对除2产生影响同理右孩子下标为 2*i2 ,即 (1i)*2 , 右孩子的的下标为2的倍数只要将2破坏成1或者0右孩子/2 的结果便就是父节点的下标 i 故而假设右孩子的节点为j 那么其父节点的下标为 (j-1)/2 (当然也可以用(j-2)/2 来计算) 综上:
1、假设父节点的下标为 i ,此父节点有两个孩子的情况下其左孩子的下标为: 2*i1 , 右孩子的下标为2*i2 ;2、假设孩子的节点为 j (无论是左孩子还是右孩子)其父节点的下标为 (j-1)/2 ;
2、链式存储结构
二叉树的链式存储结构即用链表的形式来存储二叉树的节点用指针来指示节点之间的逻辑关系在链表的结点中通常是由三个域组成数值域和左右指针域左指针域用来指向左节点右指针域用来指向右节点
而链式结构又可以分为二叉链与三叉链(此处使用的是二叉链后面会学习红黑树的时候会使用到三叉链) 注
1、三叉链就是在二叉链记录左右孩子结点的基础上再多增加一个指针域来记录其父节点的地址
2、非完全二叉树中的节点就适合使用链式结构来存储
三、堆
(一)、堆的概念
1、堆的定义 堆的物理结构本质上是顺序存储的是线性的。但在逻辑上不是线性的是的这种逻辑储存结构。 堆的这个数据结构里面的成员包括一维数组数组的容量数组元素的个数有两个直接后继。
将根节点最大的堆叫做大根堆(大堆)大堆中的任何一个父节点总是大于等于其子节点根节点为此树中最大的节点
根结点最小的堆叫做小根堆(小堆)小堆中任何一个父节点总是小于等于其子节点根节点为此树中最小的节点
注左右孩子之间并无大小关系故而大堆与小堆存储在数组中的数据不一定有序
常见的堆有二叉堆、斐波那契堆等。
2、堆的性质
1、堆中某个节点的值总是不大于或不小于其父节点中的值(堆分为大根堆、小根堆)2、堆总是一棵完全二叉树
注满二叉树是一种特殊的完全二叉树 数据结构中堆和栈的概念是完全不同于C语言中堆和栈的概念 数据结构中堆指的是用数组存储的完全二叉树而栈是可以用数组实现具有后进先出特点的数据结构另外数据结构中给的堆还可以用来做堆排序、解决TOP-K问题而C语言中的堆和栈是操作系统中存有的概念堆和栈属于内存区域的划分(利用库函数malloc、calloc、realloc 动态开辟的空间来自于堆函数调用会创建函数栈帧局部变量便是存放在栈中给的) 3、堆的特点
小根堆(小堆)中的根节点是整个二叉树中最小的节点大根堆(大堆)中的根节点是整个二叉树中最大的节点
注可以利用堆的这个特点找极值做排序并且效率高
注如果给了一个算法让我们判断它是否为堆首先是要将数组中的数据还原为堆(建堆算法)然后再进行判断
(二)、堆类型的声明
堆的本质是一个完全二叉树(底层是数组实现的动态开辟的数组需要变量size 与变量capacity)并在此基础上增加了一些要求父子节点之间的大小关系
注
1、大堆的父子节点大小关系父节点 子节点2、小堆的父子节点大小关系 父节点 子节点3、并没有约定兄弟之间的大小关系
类型声明如下
注
1、堆底层利用数组来存放数据2、利用数组下标可以找到父子节点(因为堆一定是一个完全二叉树)如果父节点的下标为i那么其左孩子的节点下标为2*i1 ,其右孩子的节点下标为 2*22如果孩子的的下标为j 那么父节点的下标为 (j-1)/2;
(三)、堆的实现
1、Heap.h 的实现 #pragma once#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.h//堆的类型的定义
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//初始化
void HPInit(HP* php);//销毁
void HPDestroy(HP* php);//交换
void Swap(HPDataType* p1, HPDataType* p2);//向上调整
void AdjustUp(HPDataType* a, int child);//push
void HPPush(HP* php, HPDataType x);//向下调整
void AdjustDown(HPDataType* a, int n, int parent);//pop
void HPPop(HP* php);//获取堆顶的数据
HPDataType HPTop(HP* php);//判空
bool HPEmpty(HP* php);注
为什么会有向上调整
堆的规则大堆其父节点子节点 小堆父节点 子节点 当你将数据放在数组的结尾的时候(size 指向的空间)要将该数据与其父节点进行比较当不符合该堆的特点的时候就进行交换以满足堆的结构规则将数据一个一个地向上调整便可以维护该堆地结构 2、Heap.c 的实现
1、初始化 //初始化
void HPInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
} 2、销毁 //销毁
void HPDestroy(HP* php)
{//释放所有动态开辟的空间assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}3、交换 //交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
} 4、向上调整
大堆 //向上调整 - 大堆 父节点 子节点
void AdjustUp(HPDataType* a, int child)
{//利用孩子的下标可以找到父节点的下标int parent (child - 1) / 2;//让子节点与父节点进行比较不符合大堆要求的就交换位置//当与根节点比较交换了之后便停止循环(最差的情况 - 比较交换到根节点)while (child0){if (a[parent] a[child])//不符合大堆 父节点子节点便交换{Swap(a[parent], a[child]);//调整child parent;parent (child - 1) / 2;}else{break;}}} 小堆 //向上调整 - 小堆 父节点 子节点
void AdjustUp(HPDataType* a, int child)
{//利用孩子的下标可以找到父节点的下标int parent (child - 1) / 2;//让子节点与父节点进行比较不符合小堆要求的就交换位置//当与根节点比较交换了之后便停止循环(最差的情况 - 比较交换到根节点)while (child0){if (a[parent] a[child])//不符合小堆 父节点子节点便交换{Swap(a[parent], a[child]);//调整child parent;parent (child - 1) / 2;}else{break;}}} 5、push //push
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-a, newcapacity*sizeof(HPDataType));if (tmp NULL){perror(HPPush realloc);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;//向上调整AdjustUp(php-a, php-size -1);}6、向下调整
逻辑分析
利用父节点的下标计算子节点的下标该父节点可能没有子节点可能只有一个子节点(即左子节点)或者有两个子节点分情况讨论假设法-先假设左孩子为两孩子中较大的节点如若只有一个孩子那么需要比较的也为左孩子让父节点与其子节点中较大或者较小(取决于堆) 来进行比较 -- 与其所有的子孙节点进行比较向下调整到右节点便停止即没有孩子的节点 —— 循环限制的条件
大堆 //向下调整 - 大堆- 让父节点与较大的那个子节点进行比较
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;}//与子祖孙节点进行比较if (a[parent] a[child]){Swap(a[parent], a[child]);//调整parent child;child parent * 2 1;}else{break;}}
}小堆 //向下调整 - 小堆- 让父节点与较小的那个子节点进行比较
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;}//与子祖孙节点进行比较if (a[parent] a[child])//小堆 父节点 子节点{Swap(a[parent], a[child]);//调整parent child;child parent * 2 1;}else{break;}}
}注大堆与小堆的向下调整的算法区别在于
1、假设法中取左右孩子中较大者还是较小者(取决于该堆是大堆还是小堆)2、父节点与其子节点的大小关系(取决于该堆是大堆还是小堆)
7、pop //pop - 堆根的数据
void HPPop(HP* php)
{//为了不破坏堆的结构删除堆根的数据首先让堆根的数据与最后一个数据进行交换//然后再使用向下调整assert(php);Swap(php-a[0], php-a[php-size]);//下标本身就比实际个数少一AdjustDown(php-a, php-size, 0);//让堆根的数据进行向下调整php-size--;
}删除的逻辑(删除的是堆根中的数据)
如果像顺序表中删除下标为0空间中的数据逻辑来实现堆中的删除 -- 将下标为0后面空间中的数据向前挪动1以覆盖下标为0空间中的数据由于堆仅仅只是规定了父子节点之间的大小关系即其兄弟之间并没有规定大小关系所以当数据向前挪动的时候父子节点关系会被改变即父子变兄弟倘若其父子节点之间的大小关系不符合堆的规定那么其结构就不能再为堆也可以重新建堆但如果每删除一个数据均要重建堆这样的消耗是非常大的
故而此处采用了另外一个逻辑将堆根中的数据与数组中最后一个数据进行交换size--然后再将堆根上的数据进行向下调整(让根节点与其子孙进行比较让根节点中的数据要符合该堆的特点)
8、获取堆顶数据 //获取堆顶的数据
HPDataType HPTop(HP* php)
{assert(php);assert(php-size);//确保堆中有数据可以获得return php-a[0];
} 9、判空 //判空
bool HPEmpty(HP* php)
{assert(php);//空为真return php-size 0;
} (四)、堆排序
1、建堆算法
在讲述堆排序之前我们先来了解一下两种建堆算法
在上述堆的实现中我们利用向上调整与向下调整来处理堆中的数据同理我们也可以利用向上调整或者向下调整来对数组中的数据进行调整让其成为堆(大堆或者小堆)
方法一利用向上调整建堆
其实就是模拟上述“堆实现”中插入push的过程只不过此处是在原数组的基础上进行建堆并没有另外创建空间来建堆
代码如下 int arr[] { 2,10,29,38,42,53,31,4,21 };int sz sizeof(arr) / sizeof(arr[0]);//建堆 - 向上调整建堆for (int i 0; i sz; i){AdjustUp(arr, i);} 注向上调整算法的复杂度为O(N^logN);
方法二利用向下调整建堆
向上调整建堆的前提所调整的节点的子树为堆
故而想要在数组中进行调整就不能像上述“堆的实现”中向上调整那样从下标为0的数据开始调整而由于叶节点没有孩子那么可以将叶节点本身就看做一个堆故而向下调整应该从最后一个非叶节点开始
最后一个非叶节点如何计算得到
最后一个叶结点的父节点便是最后一个非叶结点(可利用数组下标进行计算)
代码如下: int arr[] { 2,10,29,38,42,53,31,4,21 };
int sz sizeof(arr) / sizeof(arr[0]);
//建堆 - 向下调整建堆
for (int i (sz - 1 - 1) / 2; i 0; i--)
{AdjustDown(arr, sz, i);
} 注大堆与小堆中的向上、向下调整算法有一点差异具体可以见上面的代码(堆的实现中的向上调整与向下调整)
向下调整算法的时间复杂度为:O(N)
2、堆排序
首先我们先来思考一下倘若我们想要数组中的数据降序是需要建大堆还是小堆呢
答案是小堆因为堆中的数据并不是有序的(堆只是规定了父子节点的大小关系并没有规定兄弟节点之间的大小关系)但是堆有个特点是大堆中堆根上的数据是整个二叉树中最大的一个小堆中的堆根上的数据是整个二叉树中最小的一个
降序大数据在前面小数据在后面降序可以有两种处理方式
一是先确定大数据的位置然后依次确定次大次次大……的数据的位置二是逆向思维先确定好小数据的位置然后依次确定好次小、次次小……的数据的位置显然此处最好采用方式二的逆向思维 我们先来思考一下方式一的问题倘若排降序而你先确定好大数据的位置(大数据的对应的空间便不会再动了)就会选择建大堆, 那么抽象地理解上相当于头删再将这个空间后面的数据当作堆的话又需要重新建堆因为此时父子关系会变成兄弟关系不符合堆的大小要求如若每确定一个数据的位置都需要重新建堆的话这样的消耗是非常大此法的时间复杂度为O(N^2 ) (假设此处建堆采用的是向下调整建堆向下调整建堆的时间复杂度为O(N),而有N个数据所以此算法的时间复杂度为O(N^2)但是如果建堆采用向上调整算法的话那么此法的时间复杂度便会为O(N^2*logN)) 我们再来思考一下方式二的逆向思维排降序先确定小值的位置当然是建小堆建小堆将堆根中的数据与数组中最后一个数据进行交换并且不动这个位置的数据(相当于尾删)交换数据并没有破坏堆根子树堆的特点于是可以对堆根进行向下调整处理然后重复上述操作一个一个地确定数据地位置让其变成降序此法操作的时间复杂度为O(N*logN); 故而排降序需要建小堆同理排升序就需要建大堆
堆排降序的思路借助于“堆的实现”中删除的操作将堆根中的数据与最后一个数据进行交换此时便会将该堆中最小的数据放在后面然后进行伪删的操作(“伪删除相当于不会将其交换到后面的数据当作堆中的数据”)然后再进行向下调整重复上述操作最后在数组中的数据便是降序
代码如下 int arr[] { 2,10,29,38,42,53,31,4,21 };
int sz sizeof(arr) / sizeof(arr[0]);
//建堆算法两种均可
//建堆 - 向下调整建堆 - 排降序 - 建小堆
for (int i (sz - 1 - 1) / 2; i 0; i--)
{AdjustDown(arr, sz, i);
}建堆 - 向上调整建堆
//for (int i 0; i sz; i)
//{
// AdjustUp(arr, i);
//}//排降序
int n sz - 1;//最后数据的下标
while (n)//sz 个数据只需要处理 sz-1 次
{//交换Swap(arr[0], arr[n]);//伪删sz--;//向下调整AdjustDown(arr, sz, 0);n--;
} 注排升序同理 (五)、TOP-K 问题
TOP-K问题求数据结合中前K个最大的元素的或者最小的元素一般情况下数据量都比较大(千万、上亿级别)
例如世界500强、富豪榜、游戏中的战力排名等 我们之前解决最大或者最小的前k个数据的时候通常采用排序的方法但是如果数据量非常大(例如 14亿)这时候如果还使用排序的话消耗的是非常大的(将数据加载到内存中的时间、空间消耗以及排序操作的时间消耗)故而此时会利用堆来解决数据量非常大的TOP-K问题 假设此处需要找出14亿 人中最有钱的前10个人
如果利用上述“堆的实现”中的思路来解决这个问题先建存放了14亿个数据的一个大堆然后再利用HPTop 与 HPPop 来不断获得堆顶的数据此操作的时间复杂度为O(N),空间复杂度为O(N)
假设一个数据的大小为4byte ,那么存放14亿个数据就需要 大约4GB的内存空间(小于4GB)在内存中开辟4GB的连续空间来存放数据显然是不太可能的
解决方案一
将总数据划分成若干份(适中)多次TOP-K即可
简单来说如果此次所要TOP-K的数据有4GB 这么多那么便先1GB地将数据放入内存中然后获取前10个最大的数据……一路下来会得到40个最大的数据最后在这40个数据中找到最大的前10个即可
当然如果你觉得花1GB的内存空间来存放数据还是太大了可以将每一次所要比较的数再减少一些这样每次比较的数据便少了占用的内存也小了但是处理次数变多了势必会导致效率下降(空间换时间)
解决方案二
注假设此处有100万个数据存放在文件 data.txt 中
先读取文件中k个数据以建K个数据的小堆将文件中的数据每次读一个放在内存中然后与堆根中的数据比较比堆根的数据大便将堆根中的数据替换然后再进行向下调整
代码如下 #includestdio.h
#includeassert.h
#includestdlib.h
#includetime.h//堆的类型声明
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void CreateData()
{//打开文件 FILE* fin fopen( data.txt, w);if (fin NULL){perror(fopen);exit(-1);}//产生100万个随机数并写入文件中int n 1000000;//产生的数据个数srand((unsigned int)time(NULL));//利用时间戳产生随机的种子for (int i 0; i n; i)//写入的次数{fprintf(fin, %d\n, (rand() i) % 100000000);//产生的数字范围0~亿}//关闭文件fclose(fin);fin NULL;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}//向下调整算法 - 建小堆
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;}//小堆的特征 父节点 子节点if (a[parent] a[child]){Swap(a[parent], a[child]);//调整parent child;child parent * 2 1;}else{break;}}}void TOP_KHeap()
{int k 0;printf(请输入k);scanf(%d, k);//动态开辟一个数组的空间 - 建小堆的准备工作HPDataType* KminHeap (HPDataType*)malloc(k*sizeof(HPDataType));if (KminHeap NULL){perror(TOP_KHeap malloc);exit(-1);}//打开文件FILE * fout fopen(data.txt, r);if (fout NULL){perror(fopen);exit(-1);}//操作//先从文件中读取k个数据 - 放入创建的数组中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 x 0;//一个一个地读存放在变量x 中while (fscanf(fout, %d, x) ! EOF){if (x KminHeap[0]){//直接覆盖,再向下调整KminHeap[0] x;AdjustDown(KminHeap, k, 0);}}//此时数组KminHeap 中的k个数据为文件data.txt 中最大的前k 个数据printf(最大的前%d个数据, k);for (int i 0; i k; i){printf(%d , KminHeap[i]);}printf(\n);//换行//关闭文件fclose(fout);fout NULL;
}分析 1、造100万个随机数部分 srand 与 rand 常一起使用srand 可以利用时间戳而产生不同的种子伪随机数而 让rand 每次产生的随机数都不太一样int 可存放的数据范围为 0~ 2147483647; 故而在生成随机数最好控制在0~亿之内即(rand() i)%100000000 , 因为rand() 产生的数据额范围为0~32767 i 是为了避免产生许多重复的数%100000000 是为了控制产生的随机数的范围避免溢出减少重复值 打开文件 - 操作文件(将产生的随机值放到文件中) - 关闭文件 2、TOP-K问题的解决 主逻辑建小堆让数据与堆根中的数据进行比较(小堆中堆根的数据为此堆中最小的数据)如果文件有数据比堆根中的数据大便让此数据替换堆根中的数据再进行向下调整如此重复下去直到文件中的数据读取结束 整体逻辑梳理
1、变量的准备k、存放k 个数据的数组(所要进行建小堆的数据)
此处建立存放k个数据的数组的空间是使用malloc 动态开辟的原因k 为变量在VS编译器中不支持变长数组
2、打开文件 - 读取100万个数据3、操作文件
先将文件中的前k个数据读取放入数组KminHeap 中然后以向下调整的方式建小堆(当然也可以使用向上调整算法推荐使用向下调整算法因为向下调整建堆算法的时间复杂度更优)然后再将剩余的数据一个一个地读取放在变量x 中再与堆根中 的数据进行比较大于堆根中 的数据便将此数替换堆根中的数据如此往复直至文件中的数据读取完了
此处利用fscanf 来读取文件中 的数据当fscanf 读取失败即返回EOF此时便代表着文件中的数据均读取完了
当文件中的数据均读完的时候此时KminHeap 中k 个数据便是这个文件中100万个数据中最大的前K个
4、关闭文件
注细节由于我们在写入随机数到文件中的时候数据本身是用\n 来分割的而fscanf 在读取数据的时候遇到空格或者换行本身就会终止(scanf 遇到空格或者换行(空白字符) 便会以为是数据个数的分割)故而在读取数据的时候直接写作fscanf(fout, %d, x) 即可不用在%d 后面再增加\n ; 总结
1、树是一种非线性的数据结构它是由 n (n0) 个有限结点组成的具有层次关系的集合将此结构叫做树的原因是因为此结构像一棵倒挂的树即其根在上而叶朝下
2、二叉树(Binary Tree) 是n (n0) 个结点的有限集合该集合或者为空集(即空二叉树)或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树构成
3、堆是一种数据结构可以在其中插入、删除数据让其结构仍为堆利用堆来进行选数是非常方便的不用我们自己去建堆、调整。(注以后在c中还有一种数据结构叫做 优先级队列)
4、堆可以用来进行排序堆排序是在堆这个数据结构的基础上利用向上调整或者向下调整来建堆的(直接对数组进行建堆操作)
5、TOP-K问题
解决TOP-K问题有两种方式
1、数据量不大直接建大堆、pop数据便可此法的时间复杂度为O(N)空间复杂度为O(N)2、数据量很大的时候需要建立一个K个数的小堆让(文件中)的数据与堆根中 的数据进行比较比堆根大便进行交换(实际上是直接将堆根中的数据进行覆盖)然后再向下调整此法的时间复杂度为O(N),空间复杂度为O(1)
注方法二与方法一在效率上是差不多的但是方法二更节约空间
6、我们之前学习的时间复杂度就是纯粹地将数据存放起来。只不过在存储地时候例如数组、链表这样的结构它们各有优势而堆这种数据结构并不是单纯地用来存放数据更重要的是利用堆存放数据可以帮助我们更加高效地进行排序、解决TOP-K问题等即堆这种数据结构带有一定的功能性
堆借助于完全二叉树的特性(高度低而可以存放大量的数据)那么向上调整、向下调整的次数就比较少效率也就高(可以高效地帮助我们去选数来解决生活中地问题) 文章转载自： http://www.morning.pctql.cn.gov.cn.pctql.cn http://www.morning.hcwlq.cn.gov.cn.hcwlq.cn http://www.morning.alive-8.com.gov.cn.alive-8.com http://www.morning.yrjxr.cn.gov.cn.yrjxr.cn http://www.morning.ityi666.cn.gov.cn.ityi666.cn http://www.morning.lwqst.cn.gov.cn.lwqst.cn http://www.morning.mlpmf.cn.gov.cn.mlpmf.cn http://www.morning.hphfy.cn.gov.cn.hphfy.cn http://www.morning.tfkqc.cn.gov.cn.tfkqc.cn http://www.morning.yrjkz.cn.gov.cn.yrjkz.cn http://www.morning.jcffp.cn.gov.cn.jcffp.cn http://www.morning.hdqqr.cn.gov.cn.hdqqr.cn http://www.morning.srbbh.cn.gov.cn.srbbh.cn http://www.morning.fswml.cn.gov.cn.fswml.cn http://www.morning.rjqtq.cn.gov.cn.rjqtq.cn http://www.morning.divocn.com.gov.cn.divocn.com http://www.morning.ydrml.cn.gov.cn.ydrml.cn http://www.morning.jqhrk.cn.gov.cn.jqhrk.cn http://www.morning.skqfx.cn.gov.cn.skqfx.cn http://www.morning.jpdbj.cn.gov.cn.jpdbj.cn http://www.morning.kabaifu.com.gov.cn.kabaifu.com http://www.morning.rkwlg.cn.gov.cn.rkwlg.cn http://www.morning.rcmcw.cn.gov.cn.rcmcw.cn http://www.morning.grpbt.cn.gov.cn.grpbt.cn http://www.morning.bzkgn.cn.gov.cn.bzkgn.cn http://www.morning.zlff.cn.gov.cn.zlff.cn http://www.morning.zpyh.cn.gov.cn.zpyh.cn http://www.morning.tjwfk.cn.gov.cn.tjwfk.cn http://www.morning.jwqqd.cn.gov.cn.jwqqd.cn http://www.morning.ntgrn.cn.gov.cn.ntgrn.cn http://www.morning.jcwrb.cn.gov.cn.jcwrb.cn http://www.morning.glwyn.cn.gov.cn.glwyn.cn http://www.morning.jppb.cn.gov.cn.jppb.cn http://www.morning.qflwp.cn.gov.cn.qflwp.cn http://www.morning.qlznd.cn.gov.cn.qlznd.cn http://www.morning.tbnn.cn.gov.cn.tbnn.cn http://www.morning.ghccq.cn.gov.cn.ghccq.cn http://www.morning.dtfgr.cn.gov.cn.dtfgr.cn http://www.morning.rkzb.cn.gov.cn.rkzb.cn http://www.morning.sskkf.cn.gov.cn.sskkf.cn http://www.morning.wctqc.cn.gov.cn.wctqc.cn http://www.morning.27asw.cn.gov.cn.27asw.cn http://www.morning.jnhhc.cn.gov.cn.jnhhc.cn http://www.morning.bwdnx.cn.gov.cn.bwdnx.cn http://www.morning.bojkosvit.com.gov.cn.bojkosvit.com http://www.morning.xrftt.cn.gov.cn.xrftt.cn http://www.morning.lmctj.cn.gov.cn.lmctj.cn http://www.morning.cnbdn.cn.gov.cn.cnbdn.cn http://www.morning.tsqpd.cn.gov.cn.tsqpd.cn http://www.morning.mmsf.cn.gov.cn.mmsf.cn http://www.morning.kxxld.cn.gov.cn.kxxld.cn http://www.morning.wjlbb.cn.gov.cn.wjlbb.cn http://www.morning.dbhnx.cn.gov.cn.dbhnx.cn http://www.morning.w58hje.cn.gov.cn.w58hje.cn http://www.morning.mhmdx.cn.gov.cn.mhmdx.cn http://www.morning.xbdrc.cn.gov.cn.xbdrc.cn http://www.morning.ykrg.cn.gov.cn.ykrg.cn http://www.morning.zkqsc.cn.gov.cn.zkqsc.cn http://www.morning.dzpnl.cn.gov.cn.dzpnl.cn http://www.morning.lfqtp.cn.gov.cn.lfqtp.cn http://www.morning.sfswj.cn.gov.cn.sfswj.cn http://www.morning.dpruuode.cn.gov.cn.dpruuode.cn http://www.morning.msbmp.cn.gov.cn.msbmp.cn http://www.morning.qstkk.cn.gov.cn.qstkk.cn http://www.morning.tyklz.cn.gov.cn.tyklz.cn http://www.morning.bwznl.cn.gov.cn.bwznl.cn http://www.morning.fdlyh.cn.gov.cn.fdlyh.cn http://www.morning.fcpjq.cn.gov.cn.fcpjq.cn http://www.morning.npmx.cn.gov.cn.npmx.cn http://www.morning.ydyjf.cn.gov.cn.ydyjf.cn http://www.morning.gkjyg.cn.gov.cn.gkjyg.cn http://www.morning.jwcmq.cn.gov.cn.jwcmq.cn http://www.morning.fdjwl.cn.gov.cn.fdjwl.cn http://www.morning.dlhxj.cn.gov.cn.dlhxj.cn http://www.morning.cfccp.cn.gov.cn.cfccp.cn http://www.morning.zxfdq.cn.gov.cn.zxfdq.cn http://www.morning.xmwdt.cn.gov.cn.xmwdt.cn http://www.morning.pffx.cn.gov.cn.pffx.cn http://www.morning.lyjwb.cn.gov.cn.lyjwb.cn http://www.morning.wwklf.cn.gov.cn.wwklf.cn
