Priority Queue Decrease Function

[ChickenLegs33]

Hi! I am trying to implement a decrease key function for a Priority Queue to be used in Dijkstra's algorithm. I am new to this site, but I can upload my source files if needed. I need to know how to do only this function for an unsorted list and a heap. Thank you!

[ChickenLegs33]

I know I shouldn't double post, but not giving you more information would not be nice...

I ONLY need to implement the decrease key function in whatever possible way for use with a Dijkstra's algorithm. It all compiles as of now. The function is supposed to be like this:

Decrease-Key(x, key) – Change the key of item x in the heap to key. key must not be
greater than x’s current key value.

I thank you in advance for whatever help you can give me. Seems like I am always cursed to have one random thing I just cannot figure out.

[Lindley]

One simple way to implement decrease_key is to just remove the element from the heap, and then re-insert it with a different key. This isn't necessarily the most efficient approach, but it will work.

The standard library's heap functions (std::make_heap, std:ush_heap, std:op_heap, and the std:riority_queue container adapter) don't even include a decrease_key capability, which I find curious.

[ChickenLegs33]

One simple way to implement decrease_key is to just remove the element from the heap, and then re-insert it with a different key. This isn't necessarily the most efficient approach, but it will work.

The standard library's heap functions (std::make_heap, std:ush_heap, std:op_heap, and the std:riority_queue container adapter) don't even include a decrease_key capability, which I find curious.

Thanks for the response! I actually considered doing exactly what you said, but I could find no way to implement a remove operation, and I spent several hours trying to find a way to get that to work. I also tried finding a way to access the setKey() function from the Item class, but to no avail. I was hoping to have the function allow the user to choose a position to remove and also allow the user to choose what key to change to. With my code, I thought I could make a new instance of item and copy the position in the heap's data to the new item, and then change the key to the key specified by the user, and then delete the item at the heap position, and insert the new item. I have a clear idea of it in my head, I just can't figure out how to do it...Any ideas? (My code may not be the best implementation). I also implemented a priority queue the same way with an unsorted list but with the same problem. It may be easier to understand, so I can upload that if it may help. Though unsorted list runs slower, I am only concerned with making it work for the moment. Also, I know to use the iterator for the list implementation, so it makes more sense to me.

After digging around, I found out I could use a map to hold the positions with template <ElemType, Locator*>, but I cannot find where to put the map. My new code is now:

Item.h

class Locator
{
	public:
		int pos;
};

template<typename ElemType>
class Item
{
	private:
		int key;
		ElemType elem;
		Locator* loc;
	public:
		Item(const int k = 0, ElemType e = ElemType()) //Constructor
			: key(k), elem(e)
		{
			loc = new Locator();
		}

	//Functions
	Locator* getLoc()
	{
		return loc;
	}
	const int getKey() const
	{
		return key;
	}
	const ElemType& getElem() const
	{
		return elem;
	}
	void setKey(const int k)
	{
		key = k;
	}
	void setElem(const ElemType& e)
	{
		elem = e;
	}
};

PriorityQueue.h

#include "BinaryHeap.h"
#include "Item.h"
#include <map>

template<typename ElemType>
class PQComp
{
	public:
		int operator()(const Item<ElemType>& e1, const Item<ElemType>& e2)
		{
				return e1.getKey() - e2.getKey();
		}
};

template<typename ElemType>
class PriorityQueue
{
	protected:
		typedef map<ElemType, Locator*> hash;
		typedef Item<ElemType> item;
		typedef PQComp<ElemType> comp;

	private:
		BinaryHeap<item, comp> T;
		static const int DEF_SIZE = 8;

	public:
		PriorityQueue(int size = DEF_SIZE) //Constructor
			: T(size)
		{ }

	//Size
	int size()
	{
		return T.curSize;
	}
	
	//Empty
	bool isEmpty() const
	{
		return T.isEmpty();
	}

	//Insert
	void insertItem(const int k, const ElemType& e)
	{
		Item item(k, e);
		hash.insert(pair<ElemType, Locator*>(e, item.getLoc()));
		T.insert(item);
	}

	//Minimum Element
	const ElemType& minElement()
	{
		return T.findMin().getElem();
	}

	//Minimum Key
	const int minKey()
	{
		return T.findMin().getKey();
	}

	//Remove Minimum Element and show number of comparisons
	int removeMin()
	{
		if(!T.isEmpty())
		{
			T.deleteMin();
			return 1;
		}
		return 0;
	}

	//Remove recursively 'loc' Element and show number of comparisons
	int removeLoc(int loc)
	{
		return T.deleteMin(T.walkDown(loc)) + 1;
	}

	//Decrease Key recursively and show number of comparisons
	void decreaseKey(ElemType e, unsigned int k)
	{
		T.decreaseKey(hash[e]->pos, k);
	}
};

BinaryHeap.h

template<typename ElemType, typename Comp>
class BinaryHeap
{
	private:
		Comp comp;
		ElemType *array; //Uses an array
		int length;
		static const int DEF_SIZE = 8;
		void getNewArray(int newSize)
		{
			array = new ElemType[newSize];
			length = newSize;
		}

	public:
		int curSize;
		BinaryHeap(int size = DEF_SIZE)
		{
			curSize = 0;
			getNewArray(size);
		}
	
		ElemType& findMin()
		{
			return array[0];
		}
		bool isEmpty() const
		{
			return curSize == 0;
		}
	
		void buildHeap();
		void insert(const ElemType& x);
		void deleteMin();
		void walkUp(int hole);
		void walkDown(int hole);
		void decreaseKey(int, int);
};

//Insert
template<typename ElemType, typename Comp>
void BinaryHeap<ElemType, Comp>::insert(const ElemType& x)
{
	int hole = curSize++;
	for ( ; hole > 0 && comp(array[(hole - 1) / 2], x) > 0; hole = (hole - 1) / 2)
	{
		array[hole] = array[(hole - 1) / 2];
	}
	array[hole] = x;
}

//Delete Minimum Element
template<typename ElemType, typename Comp>
void BinaryHeap<ElemType, Comp>::deleteMin()
{
	array[0] = array[--curSize];
	walkDown(0);
}

//Walk Up
template<typename ElemType, typename Comp>
void BinaryHeap<ElemType, Comp>::walkUp(int hole)
{
	ElemType x = array[hole];
	
	for ( ; hole > 0 && comp(array[(hole - 1) / 2], x) > 0; hole = (hole - 1) / 2)
	{
		array[hole] = array[(hole-1)/2];
		array[hole].getLoc()->pos = hole;
	}
	array[hole] = x;
	array[hole].getLoc()->pos = hole;
}

//Walk Down
template<typename ElemType, typename Comp>
void BinaryHeap<ElemType, Comp>::walkDown(int hole)
{
	int child;
	ElemType key = array[hole];

	for ( ; 2 * hole + 1 < curSize; hole = child)
	{
		child = 2 * hole + 1;
		if (child != curSize-1 && comp(array[child], array[child + 1]) > 0)
		{
			child++;
		}
		else if (comp(key, array[child]) > 0)
		{
			array[hole] = array[child];
		}
		else
		{
			break;
		}
	}
	array[hole] = key;
}

template<typename ElemType, typename Comp>
void decreaseKey(int, int)
{
	array[hole].setKey(array[hole].getKey()-k);
	walkUp(hole);
}

The main is the same, and it will still work if I remove any place without the hash. I never implemented the hash, but I know the code is supposed to be this:

map<ElemType, Locator*> hash;

with the include, but I cannot find out where to put it. I know that is right, I just don't know how to do it.

Thanks again!