diff --git a/simutrans/trunk/simhalt.cc b/simutrans/trunk/simhalt.cc
index b483037e6..85b8afe86 100644
--- a/simutrans/trunk/simhalt.cc
+++ b/simutrans/trunk/simhalt.cc
@@ -59,6 +59,8 @@
 #include "utils/simrandom.h"
 #include "utils/simstring.h"
 
+#include "tpl/binary_heap_tpl.h"
+
 #include "vehicle/simpeople.h"
 
 karte_ptr_t haltestelle_t::welt;
@@ -1339,10 +1341,104 @@ sint8 haltestelle_t::is_connected(halthandle_t halt, uint8 catg_index) const
 
 
 /**
+ * Helper class that combines a vector_tpl
+ * with WEIGHT_HEAP elements and a binary_heap_tpl.
+ * If inserted node has weight less than WEIGHT_HEAP,
+ * then node is inserted in one of the vectors.
+ * If weight is larger, then node goes into the heap.
+ *
+ * WEIGHT_HEAP = 200 should be safe for even the largest games.
+ */
+template<class T> class bucket_heap_tpl
+{
+#define WEIGHT_HEAP (200)
+	vector_tpl<T> *buckets;  ///< array of vectors
+	binary_heap_tpl<T> heap; ///< the heap
+
+	uint16 min_weight; ///< current min_weight of nodes in the buckets
+	uint32 node_count; ///< total count of nodes
+public:
+	bucket_heap_tpl() : heap(128)
+	{
+		min_weight = WEIGHT_HEAP;
+		node_count = 0;
+		buckets = new vector_tpl<T> [WEIGHT_HEAP];
+	}
+
+	~bucket_heap_tpl()
+	{
+		delete [] buckets;
+	}
+
+	void insert(const T item)
+	{
+		node_count++;
+		uint16 weight = *item;
+
+		if (weight < WEIGHT_HEAP) {
+			if (weight < min_weight) {
+				min_weight = weight;
+			}
+			buckets[weight].append(item);
+		}
+		else {
+			heap.insert(item);
+		}
+	}
+
+	T pop()
+	{
+		assert(!empty());
+		node_count--;
+
+		if (min_weight < WEIGHT_HEAP) {
+			T ret = buckets[min_weight].pop_back();
+
+			while(min_weight < WEIGHT_HEAP  &&  buckets[min_weight].empty()) {
+				min_weight++;
+			}
+			return ret;
+		}
+		else {
+			return heap.pop();
+		}
+	}
+
+	void clear()
+	{
+		for(uint16 i=min_weight; i<WEIGHT_HEAP; i++) {
+			buckets[i].clear();
+		}
+		min_weight = WEIGHT_HEAP;
+		node_count = 0;
+
+		heap.clear();
+	}
+
+	uint32 get_count() const
+	{
+		return node_count;
+	}
+
+	const T& front()
+	{
+		assert(!empty());
+		if (min_weight < WEIGHT_HEAP) {
+			return buckets[min_weight].back();
+		}
+		else {
+			return heap.front();
+		}
+	}
+
+	bool empty() const { return node_count == 0; }
+};
+
+/**
  * Data for route searching
  */
 haltestelle_t::halt_data_t haltestelle_t::halt_data[65536];
-binary_heap_tpl<haltestelle_t::route_node_t> haltestelle_t::open_list;
+bucket_heap_tpl<haltestelle_t::route_node_t> haltestelle_t::open_list;
 uint8 haltestelle_t::markers[65536];
 uint8 haltestelle_t::current_marker = 0;
 /**
diff --git a/simutrans/trunk/simhalt.h b/simutrans/trunk/simhalt.h
index 686a037e9..fcdb26f1f 100644
--- a/simutrans/trunk/simhalt.h
+++ b/simutrans/trunk/simhalt.h
@@ -26,7 +26,6 @@
 
 #include "tpl/slist_tpl.h"
 #include "tpl/vector_tpl.h"
-#include "tpl/binary_heap_tpl.h"
 
 
 #define RECONNECTING (1)
@@ -54,6 +53,7 @@ class loadsave_t;
 class schedule_t;
 class player_t;
 class ware_t;
+template<class T> class bucket_heap_tpl;
 
 // -------------------------- Haltestelle ----------------------------
 
@@ -473,6 +473,9 @@ private:
 		inline uint16 operator * () const { return aggregate_weight; }
 	};
 
+	// open_list needs access to route_node_t
+	template<class T> friend class bucket_heap_tpl;
+
 	/* Extra data for route search */
 	struct halt_data_t
 	{
@@ -490,7 +493,7 @@ private:
 	static halt_data_t halt_data[65536];
 
 	// for efficient retrieval of the node with the smallest weight
-	static binary_heap_tpl<route_node_t> open_list;
+	static bucket_heap_tpl<route_node_t> open_list;
 
 	/**
 	 * Markers used in route searching to avoid processing the same halt more than once
diff --git a/simutrans/trunk/tpl/binary_heap_tpl.h b/simutrans/trunk/tpl/binary_heap_tpl.h
index 75abaa616..936dea3a0 100644
--- a/simutrans/trunk/tpl/binary_heap_tpl.h
+++ b/simutrans/trunk/tpl/binary_heap_tpl.h
@@ -35,10 +35,10 @@ public:
 	uint32 node_count;
 	uint32 node_size;
 
-	binary_heap_tpl()
+	binary_heap_tpl(uint32 size = 4096)
 	{
-		nodes = MALLOCN(T, 4096);
-		node_size = 4096;
+		nodes = MALLOCN(T, size);
+		node_size = size;
 		node_count = 0;
 	}