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,这是其中删除节点函数,丑的要死,可读性太差。希望可以把代码多分支语句优化。
分支结构有两种情况,该节点有左子树或左右子树都有。
需求是和值较小的子树进行交换。
It is recommended to write it in recursive form. I will demonstrate it using Python-like code:
The logic of get_min is not very complicated.
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
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