如何百度搜到自己的网站,餐饮小程序模板,合肥在线官网,中国企业黄页大全1.堆的概念
如果有⼀个集合 K {k0#xff0c;k1#xff0c;k2#xff0c;...#xff0c;k(n-1)} #xff0c;把它的所有元素按完全二叉树的形式存储在一个一维数组中#xff0c;并满足#xff1a;K(i)2*i1且K(i)2*i2#xff08;K(i)2*i1且K(i)2*i2 {k0k1k2...k(n-1)} 把它的所有元素按完全二叉树的形式存储在一个一维数组中并满足K(i)2*i1且K(i)2*i2K(i)2*i1且K(i)2*i2i0,1,2... 则称为小堆(或大堆)将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆
例有一组数据106570301525 2.堆的实现 1初始化堆 2堆的销毁 3交换 4堆的插入 5向上调整
为了构建小堆或大堆在插入数据时可以将插入的数据看作孩子在满足双亲的下标0(孩子的下标大于0)将孩子与双亲作对比向上调整数据
图例 向上调整算法的时间复杂度为了简化使用满二叉树来证明 则每层节点需要移动的次数为:每层结点的个数*向上移动的次数节点总共需要移动的次数为所有层节点需要移动的次数之和
T(h)2^1*12^2*22^3*3...2^(h-2)*(h-2)2^(h-1)*(h-1) ①
2*T(h)2^2*12^3*22^4*3...2^(h-1)*(h-2)2^(h)*(h-1) ②
①-②-T(h)2^12^22^3...2^(h-2)2^(h-1)-2^h*(h-1) 2^h-2-2^h*(h-1) 2^h(2-h)-2
T(h)2^h(h-2)2根据二叉树的性质n2^h-1,hlog2(n1)
得F(n)(n1)(log2(n1)-2)2,故向上调整算法的时间复杂度为O(n*log2(n)) 6打印堆 7判空 8堆的删除
删除堆顶数据就是将数组开头的元素和数组末尾的元素交换将堆中size的值减一此时堆中的结构可能被改变不再是大堆(小堆)需要将堆顶元素向下调整 9向下调整
以此时的堆顶元素为双亲在满足孩子的下标小于堆元素个数的情况下与两个孩子作对比如果没有右孩子则只和左孩子做对比不断向下调整数据
图例 向下调整算法的时间复杂度为了简化使用满二叉树来证明 则每层节点需要移动的次数为:每层结点的个数*向下移动的次数节点总共需要移动的次数为所有层节点需要移动的次数之和
T(h)2^0*(h-1)2^1*(h-2)2^2*(h-3)...2^(h-3)*22^(h-2)*1 ①
2*T(h)2^1*(h-1)2^2*(h-2)2^3*(h-3)...2^(h-2)*22^(h-1)*1 ②
②-①T(h)2^12^22^3...2^(h-2)2^(h-1)1-h 2^h-1-h
根据二叉树的性质n2^h-1,hlog2(n1)
T(n)n-log2(n1)故向下调整算法的时间复杂度为O(n) 10取堆顶元素 3.堆排序
1在数据结构堆中实现排序
创建数据结构堆将数组中的元素一一插入堆中在堆不为空的情况下循环取堆顶放入数组中再删除堆顶每次取出的堆顶都是堆中的最大值或最小值由此实现升序或降序排列 2利用堆的思想在数组中实现排序
通过向上调整或向下调整将数组排列成堆的结构若要排升序则建大堆排降序则建小堆将数组开头的元素和末尾的元素交换将此时数组开头的元素看作双亲向下调整 堆排序算法的时间复杂度为O(nlog2(n))效率高于冒泡排序
