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

It is recommended to write it in recursive form. I will demonstrate it using Python-like code:

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)

The logic of get_min is not very complicated.

Answer 2

It is recommended to read the source code of PriorityQueue. There are two functions: siftUp() and siftDown() internally. One is to float the element up, and the other is to sink the element. If you want to delete any node, then you need to add the node at the end. Go to the position where you want to delete the element, then sink, then float up again.

This was written casually when I was reviewing the data structure a few days ago. It has not been tested, but the main logic is still correct

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

Because the business logic itself is there, it is actually very difficult to reduce if branches. Moreover, the logic in each branch is not very complicated, and it does not have to be abstracted into an interface. Personal opinions are welcome Communicate