| 180 | } |
| 181 | |
| 182 | public FibNode<T> removeMin() |
| 183 | { |
| 184 | //FIB-HEAP-EXTRACT-MIN |
| 185 | //1| z = H.min |
| 186 | FibNode<T> z = min; |
| 187 | if(z != null) |
| 188 | { |
| 189 | min = delink(z); |
| 190 | |
| 191 | //3| for each child x of z |
| 192 | if (z.child != null) |
| 193 | { |
| 194 | final FibNode<T> startingNode = z.child; |
| 195 | FibNode<T> x = startingNode; |
| 196 | do |
| 197 | { |
| 198 | x.p = null;//set parrent to null, we will add to the root list later |
| 199 | //go to the next item in the list |
| 200 | x = x.right; |
| 201 | } |
| 202 | while (x != startingNode);//Yes, intentionally comparing objects. Circular link list. So once we reach the starting object we are done |
| 203 | |
| 204 | //now all the children are added to the root list in one call |
| 205 | min = merge(min, z.child); |
| 206 | z.child = null;//z has no more children |
| 207 | z.degree = 0; |
| 208 | } |
| 209 | else if (n == 1)//z had no children and was the only item in the whole heap |
| 210 | { |
| 211 | //so just set min to null |
| 212 | min = null; |
| 213 | } |
| 214 | |
| 215 | if(min != null) |
| 216 | consolidate();//this will set min correctly no matter what |
| 217 | n--; |
| 218 | } |
| 219 | |
| 220 | return z; |
| 221 | } |
| 222 | |
| 223 | public void decreaseKey(FibNode<T> x, double k) |
| 224 | { |