Click here to Skip to main content
15,886,258 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more: (untagged)
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!
Posted

1 solution

Okay, sorry. Still getting used to this. This is my Item.h file which can be consider the same as a "node" for a tree. The actual "node" that gets stored in the (Minimum) priority queue list (unsorted). Also contains a locator function.



class Locator
{
	public:
		int pos;
};

template<typename ElemType>
class Item
{
	private:
		int key;
		ElemType elem;
		Locator* loc;
	
	public:
		Item() { }
		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;
	}
};


This is the unsorted list that the priority queue is implemented from. The function I need help with is the decreaseKey function which I want to take in a int to determine which position should be changed, and the key to change it to. The rest of it works.


XML
#include <list>
#include <iostream>

using namespace std;

template<typename ElemType, typename Comp>
class List
{
    public:
        int size() const;
        bool empty() const;
        void insert(const ElemType& e);
        const ElemType& min() const;
        void deleteMin();
        void decreaseKey(const ElemType& e, int key);

    private:
        list<ElemType> ll;
        Comp comp;
};

//Size
template<typename ElemType, typename Comp>
int List<ElemType, Comp>::size() const
{
    return ll.size();
}

//Empty
template<typename ElemType, typename Comp>
bool List<ElemType, Comp>::empty() const
{
    return ll.empty();
}

//Insert
template<typename ElemType, typename Comp>
void List<ElemType, Comp>::insert(const ElemType& e)
{
    list<ElemType>::iterator i;
    i = ll.begin();
    while( i != ll.end() && !comp(e, *i))
        ++i;
    ll.insert(i,e);

}

//Minimum
template<typename ElemType, typename Comp>
const ElemType& List<ElemType, Comp>::min() const
{
    return ll.back();
}

//Remove Minimum
template<typename ElemType, typename Comp>
void List<ElemType, Comp>::deleteMin()
{
    ll.pop_back();
}

template<typename ElemType, typename Comp>
void List<ElemType, Comp>::decreaseKey(const ElemType& e, int key)
{

    list<ElemType>::iterator i;
    for(i = ll.begin(); i != ll.end(); ++i) {

    }
}



This is the actual Priority Queue file with the comparator function which can be changed from ">" (minimum) to "<" (maximum).

Function decKey should call decreaseKey from list.h and pass the items I mentioned above (key and position).



#include "List.h"
#include "Item.h"

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

template<typename ElemType>
class PriorityQueue
{
	protected:
		typedef Item<ElemType> item;
		typedef PQComp<ElemType> comp;

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

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

		//Insert
		void insertItem(const int k, const ElemType& e)
		{
			T.insert(item(k, e));
		}

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

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

		//Remove Minimum Element
		int removeMin()
		{
			if(!T.empty())
			{
				T.deleteMin();
				return 1;
			}
			return 0;
		}

		void decKey(int key, const ElemType& e)
		{
			T.decreaseKey(item(key, e), key);
		}
};


And the main.cpp file which is just a normal main file, nothing to special.

#include "PriorityQueue.h"

#include <string>
#include <iostream>

using namespace std;

int main()
{

	PriorityQueue<string> pqList; //Priority Queue based on List
	string elem;
	elem = "bdd";
	pqList.insertItem(9, elem);
	elem = "acd";
	pqList.insertItem(7, elem);
	elem = "bcd";
	pqList.insertItem(8, elem);

	pqList.decKey(2, "zzz");

	//Run 1
	cout << "Size: " << pqList.size() << endl;
	cout << "minElement: " << pqList.minElement() << endl;
	cout << "minKey: " << pqList.minKey() << endl;
	cout << "Comparisons: " << pqList.removeMin() << endl;
	cout << "Minimum removed." << endl << endl;

	//Run 2
	cout << "Size: " << pqList.size() << endl;
	cout << "minElement: " << pqList.minElement() << endl;
	cout << "minKey: " << pqList.minKey() << endl << endl;
	cout << "Comparisons: " << pqList.removeMin() << endl;
	cout << "Minimum removed." << endl << endl;

	//Run 3
	cout << "Is it empty: " << pqList.isEmpty() << endl;
	cout << "Comparisons: " << pqList.removeMin() << endl;
	cout << "Minimum removed." << endl << endl;

	//Run 4
	cout << "Size: " << pqList.size() << endl;
	cout << "Is it empty: " << pqList.isEmpty() << endl;

	return 0;
}


It all compiles right now and the only thing I haven't implemented is the decrease Key Function which I need in order to implement Dijkstra's algorithm. Thanks for all the help, and sorry if I am going about this the wrong way. Thanks for any help you can give me!
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900