首页 > 代码库 > rebalance
rebalance
rebalance a heap
⑴最大堆的插入
由于需要维持完全二叉树的形态,需要先将要插入的结点x放在最底层的最右边,插入后满 足完全二叉树的特点;
然后把x依次向上调整到合适位置满足堆的性质,例如下图中插入80,先将80放在最后,然后两次上浮到合适位置.
时间:O(logn)。 “结点上浮”
程序实现: //向最大堆中插入元素, heap:存放堆元素的数组 public static void insert(List<Integer> heap, int value) { //在数组的尾部添加 if(heap.size()==0) heap.add(0);//数组下标为0的位置不放元素 heap.add(value); //开始上升操作 // heapUp2(heap, heap.size() - 1); heapUp(heap, heap.size() - 1); } //上升,让插入的数和父节点的数值比较,当大于父节点的时候就和父节点的值相交换 public static void heapUp(List<Integer> heap, int index) { //注意由于数值是从下标为1开始,当index = 1的时候,已经是根节点了 if (index > 1) { //求出父亲的节点 int parent = index / 2; //获取相应位置的数值 int parentValue =http://www.mamicode.com/ (Integer) heap.get(parent); int indexValue =http://www.mamicode.com/ (Integer) heap.get(index); //如果父亲节点比index的数值小,就交换二者的数值 if (parentValue < indexValue) { //交换数值 swap(heap, parent, index); //递归调用 heapUp(heap, parent); } } }
⑵删除
操作原理是:当删除节点的数值时,原来的位置就会出现一个孔,填充这个孔的方法就是,
把最后的叶子的值赋给该孔并下调到合适位置,最后把该叶子删除。
如图中要删除72,先用堆中最后一个元素来35替换72,再将35下沉到合适位置,最后将叶子节点删除。
“结点下沉”
程序: /** * 删除堆中位置是index处的节点 * 操作原理是:当删除节点的数值时,原来的位置就会出现一个孔 * 填充这个孔的方法就是,把最后的叶子的值赋给该孔,最后把该叶子删除 * @param heap */ public static void delete(List<Integer> heap,int index) { //把最后的一个叶子的数值赋值给index位置 heap.set(index, heap.get(heap.size() - 1)); //下沉操作 //heapDown2(heap, index); heapDown(heap, index); //把最后一个位置的数字删除 heap.remove(heap.size() - 1); } /** * 递归实现 * 删除堆中一个数据的时候,根据堆的性质,应该把相应的位置下移,才能保持住堆性质不变 * @param heap 保持堆元素的数组 * @param index 被删除的那个节点的位置 */ public static void heapDown(List<Integer> heap, int index) { //因为第一个位置存储的是空值,不在考虑之内 int n = heap.size() - 2; //记录最大的那个儿子节点的位置 int child = -1; //2*index>n说明该节点没有左右儿子节点了,那么就返回 if (2 * index > n) { return; } //如果左右儿子都存在 else if (2 * index < n) { //定义左儿子节点 child = 2 * index; //如果左儿子小于右儿子的数值,取右儿子的下标 if ((Integer) heap.get(child) < (Integer) heap.get(child + 1)) { child++; } }//如果只有一个儿子(左儿子节点) else if (2 * index == n) { child = 2 * index; } if ((Integer) heap.get(child) > (Integer) heap.get(index)) { //交换堆中的child,和index位置的值 swap(heap, child, index); //完成交换后递归调用,继续下降 heapDown(heap, child); } }
rebalance
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。