数据结构和算法基础(四)[堆结构,堆排序,堆的常见题目:部分有序的数组排序,小根堆中,修改一个元素后仍保持大根堆,要求O(logN)]"/>
数据结构和算法基础(四)[堆结构,堆排序,堆的常见题目:部分有序的数组排序,小根堆中,修改一个元素后仍保持大根堆,要求O(logN)]
文章目录
- 堆结构
- 概念
- 前置概念
- 堆结构是什么
- heapInsert:往一个数组中按照大根堆的方式插入节点
- heapify:一个最大堆,弹出最大值后,依然维持最大堆
- 堆排序
- 把一个数组调成大根堆,可以优化成O(N):
- 为啥从下到上就减小时间复杂度呢?
- 系统实现的堆
- 比较器
- 堆的常见题目
- 部分有序的数组排序
- 小根堆中,修改一个元素后仍保持大根堆,要求O(logN)
堆结构
概念
前置概念
- 二叉树:每个节点可以有两个子节点:左子节点和右子节点,每个子节点又可以有左右孙子节点,这种结构就是二叉树
如果一个二叉树有N个节点,那么高度为logN - 完全二叉树:从上到下,从左到右,依次变满的二叉树,就是一个节点不会出现 有右子节点而没有左子节点的情况.
堆结构是什么
堆结构就是 用数组实现的完全二叉树,可以是数组的一部分形成了堆
一般是从0开始到某个下标index形成一个大根堆或者小根堆,堆的大小heapSize=index+1
如果从0下标开始,每个节点i,他的左子节点为:2i + 1,右子节点为:2i + 2, 他的父节点为 (i-1)/2;
如果从1下标开始,每个节点i,他的左子节点为:2i ,右子节点为:2i + 1, 他的父节点为 i/2;
从1下标开始的好处:可以用位运算来找子节点和父节点: i<<1, (i<<1) | 1,i>>1
一般提到堆,都会说大根堆和小根堆,不然的话说堆也没啥意义.
- 大根堆:每个节点都大于它下面的两个子节点
- 小根堆:每个节点都小于它下面的两个子节点
heapInsert:往一个数组中按照大根堆的方式插入节点
每次先插入节点到数据最后面,heapSize++
然后循环 找父节点,如果大于父节点则交换,直到小于父节点或者到堆顶了,结束循环
每次插入的时间复杂度为O(logN)
heapify:一个最大堆,弹出最大值后,依然维持最大堆
先让t = arr[0],即堆顶值;
然后arr[0] = arr[heapSize-1],heapSize–;
然后循环 找子节点中较大的那个,如果父节点小于该子节点 则交换,直到不小于任何一个子节点,或者没有子节点了,结束循环
时间复杂度为O(logN)
堆排序
简单来说就是利用堆结构的特征来排序.
给定一个数组arr[n],
- 第一步,先把数组调整成大根堆,
具体做法:
- 第一种方案从上到下heapInsert,O(N*logN):
heapSize=0,然后一个个的"heapInsert()",arr[++heapSize],直到heapSize=n-1 - 第二种方案,从底到顶heapify,O(N),见下面详细说明
- 第二步,从后到前遍历数组,依次把最大值和最后一个节点交换,然后heapSize--,heapify()
循环中,每个"当前位置"其实就是此时大根堆的最后一个节点,因为每次交换后都会heapify,所以arr[0]是此时大根堆中的最大值
直到heapSize==0时结束循环.
堆排序的时间复杂度O(N*logN),常数项其实略大
优势在于:额外空间复杂度O(1)
把一个数组调成大根堆,可以优化成O(N):
从后往前遍历,把当前节点为顶点构成的堆,改造成大根堆,其实就是heapify的操作.
为啥从下到上就减小时间复杂度呢?
整体按照每层为单位来看的话,
第一种方案是,越往下一层,节点数越多,heapPut需要比较的节点越多;
而优化后呢,是从底到顶heapify,最底层节点最多但不用heapify,越往上一层,节点越少,heapify需要比较的节点越多;
即第一种是每层点越多,每个点的操作越复杂;
第二种是每层点越少,每个点的操作越复杂.
这么一想,显然第二种更好.
下面简单推导一下时间复杂度,不是很严谨,领会精神
给定一个数组,length=n,我们把它想象成完全二叉树,一共有logN层,那么
- 这个数最底层的节点的个数是最多的,n/2 +1 ,加1可以忽略不计,就记为n/2个节点,这一层是不需要heapify的,因为没有子节点,假设"看"这个动作时间复杂度为1,那么这一层就是n/2的时间复杂度
- 倒数第二层是n/4个节点,这一层只要跟它下一层(即倒数第一层)节点heapify,复杂度:n/4 * 2
- 倒数第三层n/8,这一层只要跟它下两层heapify,复杂度n/8 * 3
- …
- 所以总体时间复杂度为:
T(n) = n/2 * 1 + n/4 * 2 + n/8 * 3 + …
那么:
2T(n) = n + n/2 * 2 + n/4 * 3 + …
两个式子错位相减,得到T(n) = n + n/2 + n/3 + …
时间复杂度就是O(N)了
系统实现的堆
PriorityQueue优先级队列,就是堆结构,默认是小根堆,如果自己实现一个比较器,就按照自定义的比较规则去比较了
啥时候用(java)语言提供的堆结构,啥时候用手写的堆结构?
取决于,你有没有动态改信息的需求!
语言提供的堆结构,如果你动态改数据,不保证依然有序
手写堆结构,因为增加了对象的位置表,所以能够满足动态改信息的需求
比较器
1)比较器的实质就是重载比较运算符
2)比较器可以很好的应用在特殊标准的排序上
3)比较器可以很好的应用在根据特殊标准排序的结构上
4)写代码变得异常容易,还用于范型编程
比较器这个玩意属于基础用法哈,加JAVA中就是实现compartor接口,并重写compare(Obj o1, Obj o2)方法,
根据定义的规则,如果希望o1排在o2前面(o1比o2优先),那么就返回负数;
如果希望o1排在o2后面,那么就返回正数;
如果认为o1和o2相等,无所谓,那就返回0.
比如排序,一般默认的都是"正序",即数小的优先排在前面;
如果希望倒序,自定义个比较器,将其规则反转,数大的优先即可;
当然也有各种各样自定义的比较器.
堆的常见题目
部分有序的数组排序
给定一个部分有序的数组,长度为n,排序后每个元素移动距离不超过k,k<n,对其排序:
- 初始化一个小根堆,长度是k+1,元素就是数据的前k+1(即0~k)个元素,此时最小值一定在这k+1个数里面,否则就最小值的移动举例就超过k了,不符合题意
- 设index=0;遍历数组剩下的部分,每次小根堆中弹出一个元素,这个元素就是当前的最小值,放入index,然后index++,然后把当前元素放入小根堆中,遍历下一个.
直到遍历完数组,结束循环.
然后遍历小根堆中剩下的元素,放入index的位置,index++
小根堆中,修改一个元素后仍保持大根堆,要求O(logN)
维护一个map,可以通过map找到堆中的元素对应的index
代码实现,to be continued…
更多推荐
数据结构和算法基础(四)[堆结构,堆排序,堆的常见题目:部分有序的数组排序,小根堆中,修改一个元素后仍保持大根堆,要求O(logN)]
发布评论