数据结构 - 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分支的話其實很難做到,而且在各個分支裡面的邏輯也不是很複雜,也沒有必須要到抽象成接口的程度.個人觀點,歡迎交流