Index: anches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinHeap.cs
===================================================================
--- /branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinHeap.cs	(revision 8540)
+++ 	(revision )
@@ -1,112 +1,0 @@
-﻿
-using System;
-using System.Collections.Generic;
-using HeuristicLab.Algorithms.GraphRouting.Interfaces;
-namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
-  public sealed class BinHeap<K, V> : IHeap<K, V>
-    where K : IComparable
-    where V : IComparable {
-    private class HeapElement {
-      public K Key { get; set; }
-      public V Value { get; set; }
-    }
-
-    private int capacity;
-    private int size;
-    private HeapElement[] data;
-
-    public BinHeap(int cap) {
-      size = 0;
-      capacity = cap;
-      data = new HeapElement[capacity];
-    }
-
-    public int Size {
-      get { return size; }
-    }
-
-    public void Insert(K key, V value) {
-      HeapElement elem = new HeapElement();
-      elem.Key = key;
-      elem.Value = value;
-      data[size] = elem;
-      HeapifyDown(size);
-      size++;
-    }
-
-    public KeyValuePair<K, V> PeekMin() {
-      if (size == 0) {
-        throw new InvalidOperationException("Heap is empty");
-      }
-      return new KeyValuePair<K, V>(data[0].Key, data[0].Value);
-    }
-
-    public K PeekMinKey() {
-      return data[0].Key;
-    }
-
-    public V PeekMinValue() {
-      return data[0].Value;
-    }
-
-    public void RemoveMin() {
-      RemoveAt(0);
-    }
-
-    public void DecreaseKey(K key, V value) {
-      for (int i = 0; i < size; i++) {
-        if (data[i].Value.CompareTo(value) == 0) {
-          RemoveAt(i);
-          Insert(key, value);
-          break;
-        }
-      }
-    }
-
-    private void RemoveAt(int idx) {
-      if (size == 1) {
-        size--;
-      } else {
-        if (idx < size - 1) {
-          Swap(idx, size - 1);
-          HeapifyUp(idx);
-        }
-        size--;
-      }
-    }
-
-    private void HeapifyDown(int start) {
-      int i = start;
-      int j = (i - 1) / 2;
-      while (i > 0 && (data[i].Key.CompareTo(data[j].Key) == -1)) {
-        Swap(i, j);
-        i = j;
-        j = (i - 1) / 2;
-      }
-    }
-
-    private void HeapifyUp(int start) {
-      int idx = start;
-      int left = 2 * idx + 1;
-      int right = 2 * idx + 2;
-      while ((left < size - 1 && data[idx].Key.CompareTo(data[left].Key) != -1) ||
-             (right < size - 1 && data[idx].Key.CompareTo(data[right].Key) != -1)) {
-        if ((right >= size - 1) || (data[left].Key.CompareTo(data[right].Key) == -1)) {
-          Swap(left, idx);
-          idx = left;
-        } else {
-          Swap(right, idx);
-          idx = right;
-        }
-        left = 2 * idx + 1;
-        right = 2 * idx + 2;
-      }
-    }
-
-    private void Swap(int i, int j) {
-      var elem = data[i];
-      data[i] = data[j];
-      data[j] = elem;
-    }
-  }
-}
Index: /branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeap.cs
===================================================================
--- /branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeap.cs	(revision 8540)
+++ /branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeap.cs	(revision 8541)
@@ -4,8 +4,8 @@
 using HeuristicLab.Algorithms.GraphRouting.Interfaces;
 namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
-  // implementation based on C++ version from Peter Sanders
-  // http://www.mpi-inf.mpg.de/~sanders/programs/spq/
-  public sealed class BinaryHeap<K, V> : IHeap<K, V> where K : IComparable {
-    private class KNElement {
+  public sealed class BinaryHeap<K, V> : IHeap<K, V>
+    where K : IComparable
+    where V : IComparable {
+    private class HeapElement {
       public K Key { get; set; }
       public V Value { get; set; }
@@ -13,20 +13,11 @@
 
     private int capacity;
-    private K supremum;
-    private int size; // index of last used element
-    private KNElement[] data;
+    private int size;
+    private HeapElement[] data;
 
-    public BinaryHeap(K sup, K infimum, int cap) {
+    public BinaryHeap(int cap) {
       size = 0;
       capacity = cap;
-      data = new KNElement[cap + 2];
-      for (int i = 0; i < cap + 2; i++) {
-        data[i] = new KNElement();
-      }
-      data[0].Key = infimum;
-      data[capacity + 1].Key = sup;
-      supremum = sup;
-      Reset();
-
+      data = new HeapElement[capacity];
     }
 
@@ -35,78 +26,86 @@
     }
 
+    public void Insert(K key, V value) {
+      HeapElement elem = new HeapElement();
+      elem.Key = key;
+      elem.Value = value;
+      data[size] = elem;
+      HeapifyDown(size);
+      size++;
+    }
+
     public KeyValuePair<K, V> PeekMin() {
       if (size == 0) {
         throw new InvalidOperationException("Heap is empty");
       }
-      return new KeyValuePair<K, V>(data[1].Key, data[1].Value);
+      return new KeyValuePair<K, V>(data[0].Key, data[0].Value);
     }
 
     public K PeekMinKey() {
-      return data[1].Key;
+      return data[0].Key;
     }
 
     public V PeekMinValue() {
-      return data[1].Value;
+      return data[0].Value;
     }
 
     public void RemoveMin() {
-      int i;
-      int l;
-      int r;
-      int smallest;
+      RemoveAt(0);
+    }
 
-      if (size <= 0) {
-        throw new InvalidOperationException("Cannot delete on an empty queue");
-      }
-
-      data[1].Key = data[size].Key;
-      data[1].Value = data[size].Value;
-
-      data[size].Key = supremum;
-      size--;
-      i = 1;
-      for (; ; ) {
-        l = (i << 1);
-        r = (i << 1) + 1;
-        if ((l <= size) && (data[l].Key.CompareTo(data[i].Key) == -1)) {
-          smallest = l;
-        } else {
-          smallest = i;
+    public void DecreaseKey(K key, V value) {
+      for (int i = 0; i < size; i++) {
+        if (data[i].Value.CompareTo(value) == 0) {
+          RemoveAt(i);
+          Insert(key, value);
+          break;
         }
-        if ((r <= size) && (data[r].Key.CompareTo(data[smallest].Key) == -1)) {
-          smallest = r;
-        }
-        if (smallest == i) break;
-        KNElement temp = data[i];
-        data[i] = data[smallest];
-        data[smallest] = temp;
-        i = smallest;
       }
     }
 
-    public void Insert(K key, V value) {
-      size++;
-      int hole = size;
-      while ((hole > 1) && (data[hole >> 1].Key.CompareTo(key) == 1)) {
-        data[hole].Key = data[hole >> 1].Key;
-        data[hole].Value = data[hole >> 1].Value;
-        hole = hole >> 1;
+    private void RemoveAt(int idx) {
+      if (size == 1) {
+        size--;
+      } else {
+        if (idx < size - 1) {
+          Swap(idx, size - 1);
+          HeapifyUp(idx);
+        }
+        size--;
       }
-      data[hole].Key = key;
-      data[hole].Value = value;
     }
 
-    public void DecreaseKey(K key, V value) {
-      throw new NotImplementedException();
+    private void HeapifyDown(int start) {
+      int i = start;
+      int j = (i - 1) / 2;
+      while (i > 0 && (data[i].Key.CompareTo(data[j].Key) == -1)) {
+        Swap(i, j);
+        i = j;
+        j = (i - 1) / 2;
+      }
     }
 
-    // reset size to 0 and fill data array with sentinels
-    private void Reset() {
-      size = 0;
-      K sup = supremum;
-      int cap = capacity;
-      for (int i = 1; i <= cap; i++) {
-        data[i].Key = sup;
+    private void HeapifyUp(int start) {
+      int idx = start;
+      int left = 2 * idx + 1;
+      int right = 2 * idx + 2;
+      while ((left < size - 1 && data[idx].Key.CompareTo(data[left].Key) != -1) ||
+             (right < size - 1 && data[idx].Key.CompareTo(data[right].Key) != -1)) {
+        if ((right >= size - 1) || (data[left].Key.CompareTo(data[right].Key) == -1)) {
+          Swap(left, idx);
+          idx = left;
+        } else {
+          Swap(right, idx);
+          idx = right;
+        }
+        left = 2 * idx + 1;
+        right = 2 * idx + 2;
       }
+    }
+
+    private void Swap(int i, int j) {
+      var elem = data[i];
+      data[i] = data[j];
+      data[j] = elem;
     }
   }
Index: /branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeapV2.cs
===================================================================
--- /branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeapV2.cs	(revision 8541)
+++ /branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeapV2.cs	(revision 8541)
@@ -0,0 +1,113 @@
+﻿
+using System;
+using System.Collections.Generic;
+using HeuristicLab.Algorithms.GraphRouting.Interfaces;
+namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
+  // implementation based on C++ version from Peter Sanders
+  // http://www.mpi-inf.mpg.de/~sanders/programs/spq/
+  public sealed class BinaryHeapV2<K, V> : IHeap<K, V> where K : IComparable {
+    private class KNElement {
+      public K Key { get; set; }
+      public V Value { get; set; }
+    }
+
+    private int capacity;
+    private K supremum;
+    private int size; // index of last used element
+    private KNElement[] data;
+
+    public BinaryHeapV2(K sup, K infimum, int cap) {
+      size = 0;
+      capacity = cap;
+      data = new KNElement[cap + 2];
+      for (int i = 0; i < cap + 2; i++) {
+        data[i] = new KNElement();
+      }
+      data[0].Key = infimum;
+      data[capacity + 1].Key = sup;
+      supremum = sup;
+      Reset();
+
+    }
+
+    public int Size {
+      get { return size; }
+    }
+
+    public KeyValuePair<K, V> PeekMin() {
+      if (size == 0) {
+        throw new InvalidOperationException("Heap is empty");
+      }
+      return new KeyValuePair<K, V>(data[1].Key, data[1].Value);
+    }
+
+    public K PeekMinKey() {
+      return data[1].Key;
+    }
+
+    public V PeekMinValue() {
+      return data[1].Value;
+    }
+
+    public void RemoveMin() {
+      int i;
+      int l;
+      int r;
+      int smallest;
+
+      if (size <= 0) {
+        throw new InvalidOperationException("Cannot delete on an empty queue");
+      }
+
+      data[1].Key = data[size].Key;
+      data[1].Value = data[size].Value;
+
+      data[size].Key = supremum;
+      size--;
+      i = 1;
+      for (; ; ) {
+        l = (i << 1);
+        r = (i << 1) + 1;
+        if ((l <= size) && (data[l].Key.CompareTo(data[i].Key) == -1)) {
+          smallest = l;
+        } else {
+          smallest = i;
+        }
+        if ((r <= size) && (data[r].Key.CompareTo(data[smallest].Key) == -1)) {
+          smallest = r;
+        }
+        if (smallest == i) break;
+        KNElement temp = data[i];
+        data[i] = data[smallest];
+        data[smallest] = temp;
+        i = smallest;
+      }
+    }
+
+    public void Insert(K key, V value) {
+      size++;
+      int hole = size;
+      while ((hole > 1) && (data[hole >> 1].Key.CompareTo(key) == 1)) {
+        data[hole].Key = data[hole >> 1].Key;
+        data[hole].Value = data[hole >> 1].Value;
+        hole = hole >> 1;
+      }
+      data[hole].Key = key;
+      data[hole].Value = value;
+    }
+
+    public void DecreaseKey(K key, V value) {
+      throw new NotImplementedException();
+    }
+
+    // reset size to 0 and fill data array with sentinels
+    private void Reset() {
+      size = 0;
+      K sup = supremum;
+      int cap = capacity;
+      for (int i = 1; i <= cap; i++) {
+        data[i].Key = sup;
+      }
+    }
+  }
+}
