首页 > 代码库 > 最小堆的建立 插入 与删除

最小堆的建立 插入 与删除

堆是完全二叉树,完全二叉树最大的特点就是 把数据储存在数组里 通过父子结点的关系来做  不用实际建树  parent=leftchild/2; leftchild=2*parent  右就加1这儿指的是序号关系,储存的时候注意是利用树的逻辑图 从上到下 从左到右编号12345....。


建堆:实际是把数据先放入数组(注意下标从1开始),对应逻辑图,写调整代码,我的基本思路是从数组末尾开始,对应元素与其父节点比较,满足条件就换值,并且对被换的调用调整函数(要单独写个调整函数)因为被换的一个是可能不满足堆的要求的。然后一个while循环这样的操作一直做到第2个元素.一个最小堆或最大堆就可以了

删除操作:把数组最后元素替换第一个,把最后一个赋个特殊值。然后调用调整函数就OK。这样的好处是数组中实际的元素保持连续的,方便操作,而且代码简单。

插入操作;同理和删除差不多,把插入的数放在数组最后(这种方法很好),调用调整函数。

 

调整函数:接收元素下标,判断它的左儿子和右儿子(通过下标关系很好找)大小,把满足条件的换上来,对被换的继续调用调整函数递归直到被换的元素满足条件,大于或小于左右儿子。细节注意数组越界等问题。

一个插入和删除操作的时间约等于调用函数的时间复杂度,调用函数最多递归树的高度次也就是logn(n个结点),那么时间这三种操作的时间复杂度就是logn。

最小堆的建立 插入 与删除