凤翔网站开发,福州城乡建设发展总公司官方网站,网上推广技巧有哪些,wordpress架构分析目录
1 堆的概念
2 堆的实现
2.1 堆的初始化和销毁
2.2 获取堆顶数据和堆的判空
2.3 堆的向上调整算法
2.4 堆的向下调整算法
2.4 堆的插入
2.5 删除堆顶数据
2.6 建堆
3 建堆的时间复杂度
3.1 向上建堆的时间复杂度
3.2向下建堆的时间复杂度
4 堆的排序 前言前面介绍了树以及二叉树及其二叉树的存储方式本文就介绍基于二叉树模式下的一种结构——堆。 1 堆的概念
堆分为大堆和小堆小堆是指每个父节点的值都小于子节点大堆是子节点的值都大于父节点 小堆是这样的大堆同理就可以了。
堆在逻辑上是完全二叉树结构实际的物理结构是数组接下来就进入到重点——堆的实现。 2 堆的实现
实现堆的时候我们不像之前实现顺序表的时候有增删查改以及指定位置的删除增加等等因为堆单纯用来存储数据是没有太大的意义的所以实现的接口也不大一样。
堆同样用结构体定义一个是数据一个是空间大小一个是有效数据个数。 typedef int HDataType;typedef struct Heap
{HDataType* arr;int size;int capacity;
}Heap;//堆的初始化
void HPInit(Heap* php);//建堆
void HPInitArray(Heap* phpHDataType* a, int n);//堆的销毁
void HPDestroy(Heap* php);//堆的插入
void HPPush(Heap* php,HDataType x);//获取堆顶数据
HDataType HPTop(Heap* hp);//堆的删除数据
void HPPop(Heap* php);//堆的判空
bool HPempty(Heap* php);//堆的向上调整算法
void AdjustUp(HDataType* arr,int child);//堆的向下调整算法
void AdjustDown(HDataType* arr,int size ,int parent);
2.1 堆的初始化和销毁
销毁和初始化与之前线性表的初始化基本上就是一样的不用过多介绍
void HPInit(Heap* php)
{assert(php);php-arr NULL;php-capacity php-size 0;
}
//堆的销毁
void HPDestroy(Heap* php)
{assert(php);free(php-arr);php-arr NULL;php-capacity php-size 0;
}2.2 获取堆顶数据和堆的判空
获取数据只需要判断堆是不是空的就行判空只需要检查size的值就可以了。
bool HPempty(Heap* php)
{assert(php);return php-size 0;
}
//获取堆顶数据
HDataType HPTop(Heap* php)
{assert(php);assert(!HPempty(php));return php-arr[0];
}
因为后面的向上调整和向下调整我们对于数据的交换用的是很频繁的所以我们单独创建一个函数用来交换数据
//交换数据
void Swap(HDataType* px, HDataType* py)
{HDataType tem *px;*px *py;*py tem;
}
2.3 堆的向上调整算法
堆的向上调整算法即是我们插入数据之后保持数据的结构依然是堆所以向上调整就是从最后一个数据入手往上依次调整如果堆是小堆那么就是子节点与父节点比较大小子节点小于父节点就交换大堆同理可得。
那么向上调整我们知道子节点如何求的父节点呢
其实通过节点之间的存储规律我们可以得到
左子节点 父节点 * 2 1右子节点 父节点 * 2 2
知道任意子节点我们就可以求父节点实际操作的时候我们求父节点的时候怎么知道子节点是左还是右呢
解决方法就是不管三七二十一父节点 (子节点 - 1) / 2不管多出来的1因为整型运算1 / 2 0所以1是被忽略了。
因为调整的次数可能不止一次可能调整到高度的一半就停止了或者是调整到了根部所以我们使用while循环循环条件就是子节点的下标因为经历一次调整后子节点会到父节点上父节点又到该节点的父节点上那么判断条件就应该是子节点的下标位置。
//堆的向上调整算法
void AdjustUp(HDataType* arr, int child)
{int parent (child - 1) / 2;//注意大小堆的写法while (child){if (arr[child] arr[parent]){Swap(arr[child],arr[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
2.4 堆的向下调整算法
如果说向上调整算法是从子节点入手那么向下调整算法就是从父节点入手父节点和子节点相互比较必然存在一个问题就是子节点可能只能只有左节点没有右节点那我们还要考虑的是两个节点谁小的问题父节点与两个子节点较小的节点比较这里可以用到假设法解决。
传进去的参数是数组堆的有效数据个数父节点的下标。
这里同样用到while循环因为是从上往下调整的所以结束条件应该是child。
为什么是child而不是parent呢因为调整到最后两层的时候parent在倒数第二次就不用动了已经调整结束了所以向下调整比向上调整有一个明显的优势是在于最后一层不是干涉时间复杂度会少很多很多后面再介绍。
假设法找两个子节点中小的那个为了防止存在越界访问比如只有一个左孩子但是child 1就访问到了右孩子就越界了所以child 1 size就是为了防止越界访问的。
最后就是进行比较交换赋值了。
//堆的向下调整算法
void AdjustDown(HDataType* arr, int size, int parent)
{int child parent * 2 1;//为什么不用child当作循环条件呢while (child size){//先找两个孩子中小的那个 假设法if (arr[child 1] arr[child] child 1 size){child;}//交换if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}
2.4 堆的插入 堆的插入很简单的就跟顺序表的插入一样的 无非是最后要保持数据依然是堆而已因为数据是在最后位置插入的所以可以用向上算法进行调整前面就是判断空间够不够不够扩容就行就没其他要注意的
//堆的插入
void HPPush(Heap* php, HDataType x)
{assert(php);//判断空间是否足够if (php-capacity php-size){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HDataType* tem (HDataType*)realloc(php-arr, sizeof(HDataType) * newcapacity);if (tem NULL){perror(realloc fail);return;}php-arr tem;php-capacity newcapacity;}php-arr[php-size] x;//插入后依然保持为堆AdjustUp(php-arr,php-size - 1);}
2.5 删除堆顶数据
删除数据都是删除的堆顶数据那么删除了之后我们该如何保持堆依然是大小堆呢我们不能直接然后面的数据往前移动一位这会让堆的数据完全乱套的结构完全变化了。
前人是思路很是清奇的。我们不妨让第一个数据和末尾的数据进行交换size--后堆顶的数据就被删除了问题是如何保持堆的结构呢你看向下调整这不就有大用了从堆顶一直往下调整呗就很清奇的这个思路一下就删除好了。
结合这个思路如果我们想要找最小次小的数据是可以模拟这个思路的后面介绍咯。
当然没有数据肯定就不能删除了。
//堆的删除数据 删除的是堆顶数据
void HPPop(Heap* php)
{//数据删除之后依然保持为堆assert(php);assert(!HPempty(php));Swap(php-arr[0], php-arr[php-size - 1]);php-size--;AdjustDown(php-arr,php-size,0);
}
2.6 建堆
建堆有两个方法一个是初始化一个堆之后进行插入数据调整操作还有一种就是初始化的这个过程就进行调整数据即创建好一个满足堆需求的数组再拷贝上去就行。
数据给好之后该赋值的也都要赋值然后就是调整数据部分我们可以选择向上调整也可以选择向下调整至于效率是向下调整优先的所以向上调整一般用的是比较少的后面介绍。
//建堆
void HPInitArray(Heap* php,HDataType* a,int n)
{assert(php);php-arr (HDataType*)malloc(sizeof(HDataType) * n);if (php-arr NULL){perror(malloc fail!);return;}memcpy(php-arr, a, sizeof(HDataType) * n);php-capacity php-size n;//向上建堆//for (int i 0; i n; i)//{// AdjustUp(php-arr,i);//}//向下建堆for (int i (php-size - 1 - 1) / 2; i 0; i--){AdjustDown(php-arr, php-size, i);}
}
向下建堆有个要注意的点就是i php-size - 1 - 1这是为了防止越界访问假设堆里面只有9个元素传进去的i就是4进入到向下调整之后child 9可是这是size指向的位置一访问就越界了。 3 建堆的时间复杂度
建堆无非就两种方式向上建堆和向下建堆两种方式看似相差不大实际上时间复杂度是相差较大的这里就来慢慢分析
计算时间复杂度之前我们不妨计算一下树的高度与节点个数之间的关系 二叉树的节点是以二次方递增的第一层有2^0个节点第二层有2^1个节点……第h层有2^(h - 1)次方个节点那么总节点个数N 2^0 2^1 2^3 …… 2^(h - 1)这里使用高中的等比求和公式可以得出N 2^h - 1那么h log(N 1)。
3.1 向上建堆的时间复杂度
时间复杂度估算即是估算每个节点执行多少次操作第一层的节点执行调整操作次数至多为0次第二层1次第三层2次第四层3次第h层 h -1 次。
总的执行次数就是该层的所有节点 * 该层节点执行的至多次数.
F( h ) 2^0 * 0 2 ^ 1 * 1 2 ^ 2 * 2 2 ^ 3 * 3 …… 2 ^ (h - 1) * (h - 1)这里利用高中的错位相减可以得到F(h) 2^(h - 2) 2那么F(N) ( N 1 ) * (log( N 1) - 2) 2。
所以向上建堆的时间复杂度就是O(N) N * log(N)。
3.2向下建堆的时间复杂度
同3.1向下建堆与向上建堆不一样的是向下建堆止步于倒数第二层这就是为什么向下建堆算法优于向上建堆算法。
节点向下调整至多调整到倒数第二层所以第一层的节点执行的次数为h - 1第二层为h - 2倒数第二层执行的次数为1次所以: F(h) 2^0 * (h - 1) 2 ^ 1 * (h - 2) 2 ^ 2 * (h - 3) …… 2 ^ (h-1) * 1结合高中的数学知识可以得到F(h) 2^h - h - 3F(N) (N 1) - log( N 1) - 3.
所以向下建堆的时间复杂度就是O(N) N - log(N)。
这样看来向下建堆的效率远高于向上建堆的效率。 4 堆的排序
堆用来存储数据意义不大排序倒是有点意思当我们想让一个数组变成升序我们是大堆还是小堆呢 一般来说小堆就是子节点大于父节点满足升序但是实际操作发现哪哪儿都是坑特别容易改变结构。
面的删除操作有着异曲同工之妙我们实现升序就选择大堆讲堆顶数据放在最后,size--就访问不了最大的数据然后选出第二大的数据再交换再size--再选择第三大的数据再交换再size--重复操作最后就实现了堆排。
//堆排
void HPsort(HDataType* arr, int size)
{for (int i (size - 1 - 1); i 0 ; i--){AdjustDown(arr,size,i);}int end size - 1;while (end){Swap(arr[0], arr[end]);AdjustDown(arr, end, 0);end--;}
}感谢阅读 文章转载自： http://www.morning.slqzb.cn.gov.cn.slqzb.cn http://www.morning.baohum.com.gov.cn.baohum.com http://www.morning.przc.cn.gov.cn.przc.cn http://www.morning.xhgcr.cn.gov.cn.xhgcr.cn http://www.morning.pycpt.cn.gov.cn.pycpt.cn http://www.morning.zybdj.cn.gov.cn.zybdj.cn http://www.morning.pqjpw.cn.gov.cn.pqjpw.cn http://www.morning.khzml.cn.gov.cn.khzml.cn http://www.morning.zcnwg.cn.gov.cn.zcnwg.cn http://www.morning.jbhhj.cn.gov.cn.jbhhj.cn http://www.morning.rkqzx.cn.gov.cn.rkqzx.cn http://www.morning.lgmty.cn.gov.cn.lgmty.cn http://www.morning.zfxrx.cn.gov.cn.zfxrx.cn http://www.morning.ndyrb.com.gov.cn.ndyrb.com http://www.morning.qynnw.cn.gov.cn.qynnw.cn http://www.morning.qbnfc.cn.gov.cn.qbnfc.cn http://www.morning.pgfkl.cn.gov.cn.pgfkl.cn http://www.morning.pcbfl.cn.gov.cn.pcbfl.cn http://www.morning.mrqwy.cn.gov.cn.mrqwy.cn http://www.morning.nbhft.cn.gov.cn.nbhft.cn http://www.morning.qywfw.cn.gov.cn.qywfw.cn http://www.morning.bhznl.cn.gov.cn.bhznl.cn http://www.morning.wgzgr.cn.gov.cn.wgzgr.cn http://www.morning.rdnpg.cn.gov.cn.rdnpg.cn http://www.morning.yrdkl.cn.gov.cn.yrdkl.cn http://www.morning.xmjzn.cn.gov.cn.xmjzn.cn http://www.morning.swsrb.cn.gov.cn.swsrb.cn http://www.morning.ggtgl.cn.gov.cn.ggtgl.cn http://www.morning.drqrl.cn.gov.cn.drqrl.cn http://www.morning.ljhnn.cn.gov.cn.ljhnn.cn http://www.morning.bgygx.cn.gov.cn.bgygx.cn http://www.morning.brscd.cn.gov.cn.brscd.cn http://www.morning.fmtfj.cn.gov.cn.fmtfj.cn http://www.morning.ltbwq.cn.gov.cn.ltbwq.cn http://www.morning.dhbyj.cn.gov.cn.dhbyj.cn http://www.morning.jpydf.cn.gov.cn.jpydf.cn http://www.morning.mrlkr.cn.gov.cn.mrlkr.cn http://www.morning.rlwgn.cn.gov.cn.rlwgn.cn http://www.morning.pmsl.cn.gov.cn.pmsl.cn http://www.morning.ktdqu.cn.gov.cn.ktdqu.cn http://www.morning.rbylq.cn.gov.cn.rbylq.cn http://www.morning.qfrsm.cn.gov.cn.qfrsm.cn http://www.morning.yksf.cn.gov.cn.yksf.cn http://www.morning.btmwd.cn.gov.cn.btmwd.cn http://www.morning.nrwr.cn.gov.cn.nrwr.cn http://www.morning.tnbsh.cn.gov.cn.tnbsh.cn http://www.morning.kqrql.cn.gov.cn.kqrql.cn http://www.morning.qxltp.cn.gov.cn.qxltp.cn http://www.morning.mzydm.cn.gov.cn.mzydm.cn http://www.morning.bkjhx.cn.gov.cn.bkjhx.cn http://www.morning.qbgdy.cn.gov.cn.qbgdy.cn http://www.morning.zjcmr.cn.gov.cn.zjcmr.cn http://www.morning.bfybb.cn.gov.cn.bfybb.cn http://www.morning.tlpgp.cn.gov.cn.tlpgp.cn http://www.morning.mgtrc.cn.gov.cn.mgtrc.cn http://www.morning.hhzdj.cn.gov.cn.hhzdj.cn http://www.morning.qhydkj.com.gov.cn.qhydkj.com http://www.morning.nmfxs.cn.gov.cn.nmfxs.cn http://www.morning.fllfc.cn.gov.cn.fllfc.cn http://www.morning.phjny.cn.gov.cn.phjny.cn http://www.morning.fzqfb.cn.gov.cn.fzqfb.cn http://www.morning.tbrnl.cn.gov.cn.tbrnl.cn http://www.morning.hmgqy.cn.gov.cn.hmgqy.cn http://www.morning.fsqbx.cn.gov.cn.fsqbx.cn http://www.morning.hjbrd.cn.gov.cn.hjbrd.cn http://www.morning.rhmpk.cn.gov.cn.rhmpk.cn http://www.morning.gidmag.com.gov.cn.gidmag.com http://www.morning.nlkhr.cn.gov.cn.nlkhr.cn http://www.morning.nmtyx.cn.gov.cn.nmtyx.cn http://www.morning.wmdbn.cn.gov.cn.wmdbn.cn http://www.morning.bztzm.cn.gov.cn.bztzm.cn http://www.morning.qlsyf.cn.gov.cn.qlsyf.cn http://www.morning.jopebe.cn.gov.cn.jopebe.cn http://www.morning.rmpkn.cn.gov.cn.rmpkn.cn http://www.morning.pwmpn.cn.gov.cn.pwmpn.cn http://www.morning.fxkgp.cn.gov.cn.fxkgp.cn http://www.morning.gjmbk.cn.gov.cn.gjmbk.cn http://www.morning.eshixi.com.gov.cn.eshixi.com http://www.morning.ysjjr.cn.gov.cn.ysjjr.cn http://www.morning.mhnrx.cn.gov.cn.mhnrx.cn
