20行的Java代码多分支语句优化

Question

 public void delete(int pos) {        Heap[pos] = Heap[size];        size--;        int current = pos;        while (hasLeaf(current)) {            if (hasDoubleLeaf(current)                    && Heap[current] > Math.min(Heap[leftChild(current)],                            Heap[rightChild(current)])) {                if (Heap[leftChild(current)] < Heap[rightChild(current)]) {                    swap(leftChild(current), current);                    current = leftChild(current);                } else {                    swap(rightChild(current), current);                    current = rightChild(current);                }            } else if (Heap[current] > Heap[leftChild(current)]) {                swap(current, leftChild(current));                current = leftChild(current);            } else{                break;            }        }    }写了一个最小heap，这是其中删除节点函数，丑的要死，可读性太差。希望可以把代码多分支语句优化。分支结构有两种情况，该节点有左子树或左右子树都有。需求是和值较小的子树进行交换。

Answer 1

建议写成递归形式，我用Python似的代码演示一下：

def get_current(current):

    if not hasleaf(current):return current

    pos = get_min(current) # 返回 0：current, -1: left, 1: right

    swap(current, pos)

    return get_current(current)

get_min的逻辑也不是很复杂。

Answer 2

建议阅读一下PriorityQueue的源码 , 内部有一个siftUp()和siftDown()两个函数, 一个是将元素浮上来, 一个是将元素沉下去, 如果要删除任意节点, 那么也就是把末尾的节点补到删除元素的位置, 然后沉下去, 再浮上来就可以了.

这个是我前几天复习数据结构随手写的, 没有经过测试, 不过主体的逻辑还算正确

public class Heap<T extends Comparable<T>>

{

    private T[] heap ;

    private int size ;

    @SuppressWarnings("unchecked")

    public Heap(int N)

    {

        heap = (T[])new Object[N] ;

        size = 0 ;

    }

    public boolean isEmpty()

    {

        return size != 0 ;

    }

    //你要实现的那个函数

    public void delete(int pos)

    {

        if(pos == size-1)

        {

            heap[pos] = null ;

            return ;

        }

        

        heap[pos] = heap[size-1] ;

        size-- ;

        

        sink(pos , heap[pos]);

        swim(pos , heap[pos]);

    }

    public void insert(T t)

    {

        swim(size , t) ;

        size++ ;

    }

    private void swim(int index , T t)

    {

        while (index > 0)

        {

            int parent = (index-1)>>>1 ;

            T e = heap[parent] ;

            if(t.compareTo(e) >= 0)

                break ;

            heap[parent] = t ;

            index = parent ;

        }

        heap[index] = t ;

    }

    public T deleteMin()

    {

        T t = heap[0] ;

        T e = heap[--size] ;

        heap[size+1] = null ;

        if(size != 0)

            sink(0 , e) ;

        return t ;

    }

    private void sink(int index , T t)

    {

        while (index<<1+1 < size)

        {

            int min = index<<1+1 ;

            if(min+1 < size && heap[min].compareTo(heap[min+1]) > 0)

                min++ ;

            if(heap[min].compareTo(t) > 0)

                break ;

            heap[index] = heap[min] ;

            index = min ;

        }

        heap[index] = t ;

    }

}

Answer 3

public void delete(int pos) {

            Heap[pos] = Heap[size];

            size--;

            int current = pos;

            while (hasLeaf(current)) {

                if (hasDoubleLeaf(current)

                        && Heap[current] > Heap[swapNode = getMinChild(current)]) {

                    swap(swapNode, current);

                    current = swapNode;

                } else if (Heap[current] > Heap[leftChild(current)]) {

                    swap(current, leftChild(current));

                    current = leftChild(current);

                } else{

                    break;

                }

            }

        }

    }

    

    private int getMinChild(int current){

        return Heap[leftChild(current)] < Heap[rightChild(current)]? leftChild(current):rightChild(current);

    }

因为本身的业务逻辑就在那里,所以想从减少if分支的话其实很难做到,而且在各个分支里面的逻辑也不是很复杂,也没有必须要到抽象成接口的程度.个人观点,欢迎交流