首页 > 代码库 > 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