Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeapV3.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeapV3.cs	(revision 8546)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeapV3.cs	(revision 8546)
@@ -0,0 +1,130 @@
+﻿
+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/
+  // Fast Binary Heap
+  public sealed class BinaryHeapV3<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 BinaryHeapV3(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() {
+      // first move up elements on a min-path
+      int hole = 1;
+      int succ = 2;
+      int sz = size;
+      KNElement[] dat = data;
+
+      while (succ < sz) {
+        K key1 = dat[succ].Key;
+        K key2 = dat[succ + 1].Key;
+        if (key1.CompareTo(key2) > 0) {
+          succ++;
+          dat[hole].Key = key2;
+          dat[hole].Value = dat[succ].Value;
+        } else {
+          dat[hole].Key = key1;
+          dat[hole].Value = dat[succ].Value;
+        }
+        hole = succ;
+        succ <<= 1;
+      }
+
+      // bubble up rightmost element
+      K bubble = dat[sz].Key;
+      int pred = hole >> 1;
+      while (dat[pred].Key.CompareTo(bubble) > 0) {
+        //dat[hole] = dat[pred];
+        dat[hole].Key = dat[pred].Key;
+        dat[hole].Value = dat[pred].Value;
+
+        hole = pred;
+        pred >>= 1;
+      }
+
+      // finally move data to hole
+      dat[hole].Key = bubble;
+      dat[hole].Value = dat[sz].Value;
+
+      dat[size].Key = supremum; // mark as deleted
+      size = sz - 1;
+    }
+
+    public void Insert(K key, V value) {
+      KNElement[] dat = data;
+      size++;
+
+      int hole = size;
+      int pred = hole >> 1;
+      K predKey = dat[pred].Key;
+
+      while (predKey.CompareTo(key) > 0) {  // must terminate due to sentinel at 0
+        dat[hole].Key = predKey;
+        dat[hole].Value = dat[pred].Value;
+        hole = pred;
+        pred >>= 1;
+        predKey = dat[pred].Key;
+      }
+
+      // finally move data to hole
+      dat[hole].Key = key;
+      dat[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;
+      }
+    }
+  }
+}
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs	(revision 8546)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs	(revision 8546)
@@ -0,0 +1,38 @@
+﻿using System;
+using HeuristicLab.Algorithms.GraphRouting.Interfaces;
+
+namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
+  public sealed class FibonacciHeap<K, V> : IHeap<K, V>
+    where K : IComparable
+    where V : IComparable {
+
+
+    public int Size {
+      get { throw new NotImplementedException(); }
+    }
+
+    public System.Collections.Generic.KeyValuePair<K, V> PeekMin() {
+      throw new NotImplementedException();
+    }
+
+    public K PeekMinKey() {
+      throw new NotImplementedException();
+    }
+
+    public V PeekMinValue() {
+      throw new NotImplementedException();
+    }
+
+    public void Insert(K key, V value) {
+      throw new NotImplementedException();
+    }
+
+    public void DecreaseKey(K key, V value) {
+      throw new NotImplementedException();
+    }
+
+    public void RemoveMin() {
+      throw new NotImplementedException();
+    }
+  }
+}
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/Heap4.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/Heap4.cs	(revision 8546)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/Heap4.cs	(revision 8546)
@@ -0,0 +1,192 @@
+﻿
+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 Heap4<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 int finalLayerSize; // size of first layer with free space
+    private int finalLayerDist; // distance to end of layer
+    //private KNElement[] rawData;
+    private KNElement[] data;    // alligned version of rawData
+
+    public Heap4(K sup, K infimum, int cap) {
+      capacity = cap;
+      supremum = sup;
+      data = new KNElement[capacity + 4];
+
+      for (int i = 0; i < capacity + 4; i++) {
+        data[i] = new KNElement();
+      }
+
+      data[0].Key = infimum; // sentinel
+      data[capacity + 1].Key = supremum;
+      data[capacity + 2].Key = supremum;
+      data[capacity + 3].Key = supremum;
+      Reset();
+    }
+
+    public int Size {
+      get { return size; }
+    }
+
+    public K Supremum {
+      get { return data[capacity + 1].Key; }
+    }
+
+    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() {
+      K minKey;
+      K otherKey;
+      int delta;
+
+      // first move up elements on a min-path
+      int hole = 1;
+      int succ = 2;
+      int layerSize = 4;
+      int layerPos = 0;
+      int sz = size;
+      size = sz - 1;
+      finalLayerDist++;
+      if (finalLayerDist == finalLayerSize) {
+        finalLayerSize >>= 2;
+        finalLayerDist = 0;
+      }
+
+      while (succ < sz) {
+        minKey = data[succ].Key;
+        delta = 0;
+
+        otherKey = data[succ + 1].Key;
+        if (otherKey.CompareTo(minKey) < 0) {
+          minKey = otherKey;
+          delta = 1;
+        }
+        otherKey = data[succ + 2].Key;
+        if (otherKey.CompareTo(minKey) < 0) {
+          minKey = otherKey;
+          delta = 2;
+        }
+        otherKey = data[succ + 3].Key;
+        if (otherKey.CompareTo(minKey) < 0) {
+          minKey = otherKey;
+          delta = 3;
+        }
+        succ += delta;
+        layerPos += delta;
+
+        // move min successor up
+        data[hole].Key = minKey;
+        data[hole].Value = data[succ].Value;
+
+        // step to next layer
+        hole = succ;
+        succ = succ - layerPos + layerSize; // beginning of next layer
+        layerPos <<= 2;
+        succ += layerPos; // now correct value
+        layerSize <<= 2;
+      }
+
+      // bubble up rightmost element
+      K bubble = data[sz].Key;
+      layerSize >>= 2; // now size of hole's layer
+      layerPos >>= 2; // now pos of hole within its layer
+
+      int layerDist = layerSize - layerPos - 1; // hole's dist to end of layer
+      int pred = hole + layerDist - layerSize; // end of pred's layer for now
+      layerSize >>= 2; // now size of pred's layer
+      layerDist >>= 2; // now pred's pos in layer
+      pred = pred - layerDist; // finally preds index
+
+      while (data[pred].Key.CompareTo(bubble) > 0) {  // must terminate since inf at root
+        data[hole].Key = data[pred].Key;
+        data[hole].Value = data[pred].Value;
+        hole = pred;
+        pred = hole + layerDist - layerSize; // end of hole's layer for now
+        layerSize >>= 2;
+        layerDist >>= 2;
+        pred = pred - layerDist; // finally preds index
+      }
+
+      // finally move data to hole
+      data[hole].Key = bubble;
+      data[hole].Value = data[sz].Value;
+
+      data[sz].Key = Supremum; // mark as deleted
+    }
+
+    public void Insert(K key, V value) {
+      int layerSize = finalLayerSize;
+      int layerDist = finalLayerDist;
+      finalLayerDist--;
+
+      if (finalLayerDist == -1) { // layer full
+        // start next layer
+        finalLayerSize <<= 2;
+        finalLayerDist = finalLayerSize - 1;
+      }
+
+      size++;
+
+      int hole = size;
+      int pred = hole + layerDist - layerSize; // end of pred's layer for now
+      layerSize >>= 2; // now size of pred's layer
+      layerDist >>= 2;
+      pred = pred - layerDist; // finally preds index
+      K predKey = data[pred].Key;
+      while (predKey.CompareTo(key) > 0) {
+        data[hole].Key = predKey;
+        data[hole].Value = data[pred].Value;
+        hole = pred;
+        pred = hole + layerDist - layerSize; // end of pred's layer for now
+        layerSize >>= 2; // now isze of pred's layer
+        layerDist >>= 2;
+        pred = pred - layerDist; // finally preds index
+        predKey = data[pred].Key;
+      }
+
+      // finally move data to hole
+      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;
+      finalLayerSize = 1;
+      finalLayerDist = 0;
+      K sup = Supremum;
+      int cap = capacity;
+      for (int i = 1; i <= cap; i++) {
+        data[i].Key = sup;
+      }
+    }
+  }
+}
