20行的Java代码多分支语句优化

 public void deleteint pos { Heap[pos] = Heap[size]; size--; int current = pos; while hasLeafcurrent { if hasDoubleLeafcurrent && Heap[current] > Math.minHeap[leftChildcurrent], Heap[rightChildcurrent] { if Heap[leftChildcurrent] < Heap[rightChildcurrent] { swapleftChildcurrent, current; current = leftChildcurrent; } else { swaprightChildcurrent, current; current = rightChildcurrent; } } else if Heap[current] > Heap[leftChildcurrent] { swapcurrent, leftChildcurrent; current = leftChildcurrent; } else{ break; } } }

写了一个最小heap,这是其中删除节点函数,丑的要死,可读性太差。希望可以把代码多分支语句优化。
分支结构有两种情况,该节点有左子树或左右子树都有。
需求是和值较小的子树进行交换。

建议写成递归形式,我用Python似的代码演示一下:

def get_currentcurrent: if not hasleafcurrent:return current pos = get_mincurrent # 返回 0:current, -1: left, 1: right swapcurrent, pos return get_currentcurrent

get_min的逻辑也不是很复杂。

建议阅读一下PriorityQueue的源码 , 内部有一个siftUp和siftDown两个函数, 一个是将元素浮上来, 一个是将元素沉下去, 如果要删除任意节点, 那么也就是把末尾的节点补到删除元素的位置, 然后沉下去, 再浮上来就可以了.

这个是我前几天复习数据结构随手写的, 没有经过测试, 不过主体的逻辑还算正确

public class Heap<T extends Comparable<T>>
{ private T[] heap ; private int size ; @SuppressWarnings"unchecked" public Heapint N { heap = T[]new Object[N] ; size = 0 ; } public boolean isEmpty { return size != 0 ; } //你要实现的那个函数 public void deleteint pos { ifpos == size-1 { heap[pos] = null ; return ; } heap[pos] = heap[size-1] ; size-- ; sinkpos , heap[pos]; swimpos , heap[pos]; } public void insertT t { swimsize , t ; size++ ; } private void swimint index , T t { while index > 0 { int parent = index-1>>>1 ; T e = heap[parent] ; ift.compareToe >= 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 ; ifsize != 0 sink0 , e ; return t ; } private void sinkint index , T t { while index<<1+1 < size { int min = index<<1+1 ; ifmin+1 < size && heap[min].compareToheap[min+1] > 0 min++ ; ifheap[min].compareTot > 0 break ; heap[index] = heap[min] ; index = min ; } heap[index] = t ; }
}

public void deleteint pos { Heap[pos] = Heap[size]; size--; int current = pos; while hasLeafcurrent { if hasDoubleLeafcurrent && Heap[current] > Heap[swapNode = getMinChildcurrent] { swapswapNode, current; current = swapNode; } else if Heap[current] > Heap[leftChildcurrent] { swapcurrent, leftChildcurrent; current = leftChildcurrent; } else{ break; } } } } private int getMinChildint current{ return Heap[leftChildcurrent] < Heap[rightChildcurrent]? leftChildcurrent:rightChildcurrent; }

因为本身的业务逻辑就在那里,所以想从减少if分支的话其实很难做到,而且在各个分支里面的逻辑也不是很复杂,也没有必须要到抽象成接口的程度.个人观点,欢迎交流

发表评论

电子邮件地址不会被公开。 必填项已用*标注