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分支的话其实很难做到,而且在各个分支里面的逻辑也不是很复杂,也没有必须要到抽象成接口的程度.个人观点,欢迎交流