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):&nbsp; &nbsp; if not hasleaf(current):return current&nbsp; &nbsp; pos = get_min(current) # 返回 0：current, -1: left, 1: right&nbsp; &nbsp; swap(current, pos)&nbsp; &nbsp; return get_current(current)get_min的逻辑也不是很复杂。

Answer 2

建议阅读一下PriorityQueue的源码 , 内部有一个siftUp()和siftDown()两个函数, 一个是将元素浮上来, 一个是将元素沉下去, 如果要删除任意节点, 那么也就是把末尾的节点补到删除元素的位置, 然后沉下去, 再浮上来就可以了.这个是我前几天复习数据结构随手写的, 没有经过测试, 不过主体的逻辑还算正确public class Heap<T extends Comparable<T>>{&nbsp; &nbsp; private T[] heap ;&nbsp; &nbsp; private int size ;&nbsp; &nbsp; @SuppressWarnings("unchecked")&nbsp; &nbsp; public Heap(int N)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; heap = (T[])new Object[N] ;&nbsp; &nbsp; &nbsp; &nbsp; size = 0 ;&nbsp; &nbsp; }&nbsp; &nbsp; public boolean isEmpty()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; return size != 0 ;&nbsp; &nbsp; }&nbsp; &nbsp; //你要实现的那个函数&nbsp; &nbsp; public void delete(int pos)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(pos == size-1)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heap[pos] = null ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return ;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; heap[pos] = heap[size-1] ;&nbsp; &nbsp; &nbsp; &nbsp; size-- ;&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; sink(pos , heap[pos]);&nbsp; &nbsp; &nbsp; &nbsp; swim(pos , heap[pos]);&nbsp; &nbsp; }&nbsp; &nbsp; public void insert(T t)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; swim(size , t) ;&nbsp; &nbsp; &nbsp; &nbsp; size++ ;&nbsp; &nbsp; }&nbsp; &nbsp; private void swim(int index , T t)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; while (index > 0)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int parent = (index-1)>>>1 ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; T e = heap[parent] ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(t.compareTo(e) >= 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heap[parent] = t ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index = parent ;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; heap[index] = t ;&nbsp; &nbsp; }&nbsp; &nbsp; public T deleteMin()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; T t = heap[0] ;&nbsp; &nbsp; &nbsp; &nbsp; T e = heap[--size] ;&nbsp; &nbsp; &nbsp; &nbsp; heap[size+1] = null ;&nbsp; &nbsp; &nbsp; &nbsp; if(size != 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sink(0 , e) ;&nbsp; &nbsp; &nbsp; &nbsp; return t ;&nbsp; &nbsp; }&nbsp; &nbsp; private void sink(int index , T t)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; while (index<<1+1 < size)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int min = index<<1+1 ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(min+1 < size && heap[min].compareTo(heap[min+1]) > 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min++ ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(heap[min].compareTo(t) > 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heap[index] = heap[min] ;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index = min ;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; heap[index] = t ;&nbsp; &nbsp; }}

Answer 3

public void delete(int pos) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Heap[pos] = Heap[size];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; size--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int current = pos;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (hasLeaf(current)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (hasDoubleLeaf(current)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; && Heap[current] > Heap[swapNode = getMinChild(current)]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; swap(swapNode, current);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current = swapNode;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else if (Heap[current] > Heap[leftChild(current)]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; swap(current, leftChild(current));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; current = leftChild(current);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; private int getMinChild(int current){&nbsp; &nbsp; &nbsp; &nbsp; return Heap[leftChild(current)] < Heap[rightChild(current)]? leftChild(current):rightChild(current);&nbsp; &nbsp; }因为本身的业务逻辑就在那里,所以想从减少if分支的话其实很难做到,而且在各个分支里面的逻辑也不是很复杂,也没有必须要到抽象成接口的程度.个人观点,欢迎交流