Changeset 8572
 Timestamp:
 09/04/12 18:26:40 (11 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs
r8546 r8572 1 1 using System; 2 using System.Collections.Generic; 2 3 using HeuristicLab.Algorithms.GraphRouting.Interfaces; 3 4 … … 7 8 where V : IComparable { 8 9 10 private HeapNode min; 11 private int size; 9 12 10 13 public int Size { 11 get { throw new NotImplementedException(); }14 get { return size; } 12 15 } 13 16 14 public System.Collections.Generic.KeyValuePair<K, V> PeekMin() { 15 throw new NotImplementedException(); 17 public FibonacciHeap() { 18 size = 0; 19 min = null; 20 } 21 22 public KeyValuePair<K, V> PeekMin() { 23 if (size == 0) { 24 throw new InvalidOperationException("Heap is empty"); 25 } 26 KeyValuePair<K, V> pair = new KeyValuePair<K, V>(min.Key, min.Value); 27 return pair; 16 28 } 17 29 18 30 public K PeekMinKey() { 19 throw new NotImplementedException(); 31 if (size == 0) { 32 throw new InvalidOperationException("Heap is empty"); 33 } 34 return min.Key; 20 35 } 21 36 22 37 public V PeekMinValue() { 23 throw new NotImplementedException(); 38 if (size == 0) { 39 throw new InvalidOperationException("Heap is empty"); 40 } 41 return min.Value; 24 42 } 25 43 26 44 public void Insert(K key, V value) { 27 throw new NotImplementedException(); 45 HeapNode n = new HeapNode(key, value); 46 if (min == null) { 47 min = n; 48 } else { 49 n.Right = min; 50 n.Left = min.Left; 51 n.Right.Left = n; 52 n.Left.Right = n; 53 if (n.Key.CompareTo(min.Key) < 0) { 54 min = n; 55 } 56 } 57 size++; 28 58 } 29 59 … … 33 63 34 64 public void RemoveMin() { 35 throw new NotImplementedException(); 65 if (size == 0) { 66 throw new InvalidOperationException("Heap is empty"); 67 } 68 HeapNode z = min; 69 if (z.Child != null) { 70 // set all z's childs parent to null ... 71 z.Child.Parent = null; 72 HeapNode x = z.Child.Right; 73 while (x != z.Child) { 74 x.Parent = null; 75 x = x.Right; 76 } 77 // ... and make all of them roots 78 HeapNode minLeft = min.Left; 79 min.Left = z.Child.Left; 80 min.Left.Right = min; 81 z.Child.Left = minLeft; 82 minLeft.Right = z.Child; 83 } 84 85 // remove z frome root list 86 z.Left.Right = z.Right; 87 z.Right.Left = z.Left; 88 89 if (z == z.Right) { 90 min = null; 91 } else { 92 // point min to a node other than z 93 // (not necessarily going to be the new minimum) 94 min = z.Right; 95 Consolidate(); 96 } 97 size; 98 99 //var zNode = new KeyValuePair<K, V>(z.Key, z.Value); 100 z = null; 101 //return zNode; 102 } 103 104 private void Link(HeapNode y, HeapNode z) { 105 y.Left.Right = y.Right; 106 y.Right.Left = y.Left; 107 108 y.Parent = z; 109 if (z.Child == null) { 110 z.Child = y; 111 y.Right = y; 112 y.Left = y; 113 } else { 114 y.Left = z.Child; 115 y.Right = z.Child.Right; 116 z.Child.Right = y; 117 y.Right.Left = y; 118 } 119 z.Degree++; 120 y.Mark = false; 121 } 122 123 private void Consolidate() { 124 //TODO: explain magic number 125 HeapNode[] A = new HeapNode[45]; 126 HeapNode start = min; 127 HeapNode w = min; 128 129 do { 130 HeapNode x = w; 131 HeapNode nextW = w.Right; 132 int d = x.Degree; 133 134 while (A[d] != null) { 135 HeapNode y = A[d]; // another node with the same degree as x 136 if (x.Key.CompareTo(y.Key) > 0) { 137 // exchange x <> y 138 HeapNode tmp = x; 139 x = y; 140 y = tmp; 141 } 142 if (y == start) { 143 start = start.Right; 144 } 145 if (y == nextW) { 146 nextW = nextW.Right; 147 } 148 Link(y, x); 149 A[d] = null; 150 d++; 151 } 152 153 A[d] = x; 154 w = nextW; 155 } while (w != start); 156 157 min = null; 158 159 for (int i = 0; i < 45; i++) { 160 if (A[i] != null) { 161 HeapNode n = A[i]; 162 if (min == null) { 163 min = n; 164 } else { 165 if (n.Key.CompareTo(min.Key) < 0) { 166 min = n; 167 } 168 } 169 } 170 } 171 } 172 173 private class HeapNode { 174 public K Key; 175 public V Value; 176 public int Degree; 177 public bool Mark; 178 public HeapNode Left; 179 public HeapNode Right; 180 public HeapNode Parent; 181 public HeapNode Child; 182 183 public HeapNode(K key, V value) { 184 this.Key = key; 185 this.Value = value; 186 this.Right = this; 187 this.Left = this; 188 this.Parent = null; 189 this.Child = null; 190 this.Degree = 0; 191 this.Mark = false; 192 } 36 193 } 37 194 }
Note: See TracChangeset
for help on using the changeset viewer.