Anonymous

	//a  minimum priority queue implemented with a binary heap
	class PriorityQueue(T)
	{
		private Element!T[] data; //binary heap
		private size_t[T] lookup; //hash-map used to look up the indices
		private size_t size;

		this()
		{
			data = new Element!T[6];
			size = 0;

		}

		//finds the item using the lookup associative array, changes the priority, and moves the item to the correct index
		bool decreaseKey(T item, double newKey)
		{
			//check to be sure item is in the priority queue
			if(!member(item,lookup.keys))
			{
				return false;
			}
			else
			{
				size_t index  = lookup[item]; //finds the item index

				Element!T temp = data[index]; //temp is the increased item
				temp.priority = newKey; //new priority assigned

				//moves the item to the correct index
				while(index>1 && data[up(index)].priority > newKey )
				{
					data[index] = data[up(index)]; //reassigns lower position
					lookup[data[up(index)].item] = index;//updates lookup

					index = up(index);//unoccupied position	
				}

				//assign index to both array
				data[index] = temp;
				lookup[temp.item] = index;

				return true;
			}
		}

		// a helper function for decreaseKey
		private bool member(T)(T val, T[] group)
		{
			foreach(i;group)
			{
				if(i == val)
					return true;
			}
			return false;
		}	

		//adds an element to the priority queue
		void insert(T x, double prio)
		{		
			++size;

			//adds array space as necessary
			if(data.length == size)
				data.length*=2;

			size_t i = size; // starts looping variable at the bottom of the heap

			//works up the array to the correct priority position
			while(i>1 && data[up(i)].priority > prio)
			{
				data[i] = data[up(i)];
				lookup[data[up(i)].item] = i;

				i = up(i); // i is now an empty position	
			}	

			//assigns the element to the correct index
			data[i] = Element!T(x,prio);
			lookup[x] = i;	

		}	

		//removes and returns the root of the heap and reorders the heap	
		T extract_min()
		{
			enforce(size>0, "Priority Queue: Queue must contain at least one element to extract_Min");

			lookup.remove(data[1].item);
			lookup[data[size].item] = 1;

			T min = data[1].item;
			data[1] = data[size]; //puts last element at the root position
			--size;

			heapify(1); //reorders the heap
			return min;

		}

		//reorders the heap, treating i as the root
		private void heapify(size_t i)
		{
			double top_prio = data[i].priority;
			size_t index = i;

			//checks if left is in bounds and if the priority of current is greater than left
			if(left(i)<=size && data[left(i)].priority<top_prio)
			{
				index = left(i);	
				top_prio = data[index].priority;
			}
			if(right(i)<=size && data[right(i)].priority<top_prio)
			{
				index = right(i);
				top_prio = data[index].priority;
			}

			//swaps the root element with either left or right
			if(index != i)
			{
				swap(data[i],data[index]);

				//changes up the lookup array
				Element!T temp = data[i];
				size_t temp_index = lookup[data[i].item];
				lookup[data[i].item] = lookup[data[index].item];
				lookup[data[index].item] = temp_index;

				heapify(index); //recursive call with updated root
			}	
		}

		bool is_empty()
		{
			return size==0;
		}	

		//functions which return tree indices
		private size_t up(size_t pos)
		{
			return(pos/2);
		}

		private size_t left(size_t pos)
		{
			return(2*pos);
		}

		private size_t right(size_t pos)
		{
			return(2*pos+1);
		}	
	}	

	//helper struct which contains a T item and a priority used for comparisons
	struct Element(T)
	{
		T item;
		double priority;

		this(T i, double p)
		{
			item = i;
			priority = p;
		}

	}