| 58 | } |
| 59 | |
| 60 | @Test |
| 61 | public void testDecreaseKey() |
| 62 | { |
| 63 | System.out.println("decreaseKey"); |
| 64 | FibHeap<Character> h1 = new FibHeap<Character>(); |
| 65 | List<FibHeap.FibNode<Character>> nodes = new ArrayList<FibHeap.FibNode<Character>>(); |
| 66 | |
| 67 | List<Character> expectedOrder = new ArrayList<Character>(); |
| 68 | for(char c = 'A'; c < 'z'; c++) |
| 69 | { |
| 70 | nodes.add(h1.insert(c, c)); |
| 71 | expectedOrder.add(0, c); |
| 72 | } |
| 73 | Collections.shuffle(nodes); |
| 74 | for(FibHeap.FibNode<Character> node : nodes) |
| 75 | h1.decreaseKey(node, -node.value); |
| 76 | |
| 77 | assertEquals(expectedOrder.size(), h1.size()); |
| 78 | int pos = 0; |
| 79 | while(h1.size() > 0) |
| 80 | { |
| 81 | FibHeap.FibNode<Character> min = h1.removeMin(); |
| 82 | assertEquals(expectedOrder.get(pos), min.value); |
| 83 | pos++; |
| 84 | } |
| 85 | } |
| 86 | /** |
| 87 | * Test of union method, of class FibHeap. |
| 88 | */ |