数据结构 - 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

Adalah disyorkan untuk menulisnya dalam bentuk rekursif saya akan menunjukkannya menggunakan kod seperti 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)

Logik get_min tidak begitu rumit.

Answer 2

Adalah disyorkan untuk membaca kod sumber PriorityQueue Terdapat dua fungsi: siftUp() dan siftDown(). nod, maka anda perlu memadamkan nod terakhir. Nod ditambahkan pada kedudukan di mana elemen telah dipadamkan, kemudian tenggelam dan terapung semula

Ini ditulis secara santai semasa saya menyemak struktur data beberapa hari yang lalu Ia belum diuji, tetapi logik utamanya agak betul

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);
    }

Oleh kerana logik perniagaan itu sendiri ada, ia sebenarnya sangat sukar untuk mengurangkan if cawangan Selain itu, logik di setiap cawangan tidak begitu rumit, dan ia tidak perlu disarikan ke dalam antara muka , dialu-alukan untuk bertukar