首页 > 代码库 > 最小堆的建立 插入 与删除
最小堆的建立 插入 与删除
堆是完全二叉树,完全二叉树最大的特点就是 把数据储存在数组里 通过父子结点的关系来做 不用实际建树 parent=leftchild/2; leftchild=2*parent 右就加1这儿指的是序号关系,储存的时候注意是利用树的逻辑图 从上到下 从左到右编号12345....。
建堆:实际是把数据先放入数组(注意下标从1开始),对应逻辑图,写调整代码,我的基本思路是从数组末尾开始,对应元素与其父节点比较,满足条件就换值,并且对被换的调用调整函数(要单独写个调整函数)因为被换的一个是可能不满足堆的要求的。然后一个while循环这样的操作一直做到第2个元素.一个最小堆或最大堆就可以了
删除操作:把数组最后元素替换第一个,把最后一个赋个特殊值。然后调用调整函数就OK。这样的好处是数组中实际的元素保持连续的,方便操作,而且代码简单。
插入操作;同理和删除差不多,把插入的数放在数组最后(这种方法很好),调用调整函数。
调整函数:接收元素下标,判断它的左儿子和右儿子(通过下标关系很好找)大小,把满足条件的换上来,对被换的继续调用调整函数递归直到被换的元素满足条件,大于或小于左右儿子。细节注意数组越界等问题。
一个插入和删除操作的时间约等于调用函数的时间复杂度,调用函数最多递归树的高度次也就是logn(n个结点),那么时间这三种操作的时间复杂度就是logn。
最小堆的建立 插入 与删除
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。