12,753,418 members (34,943 online)
Rate this:
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 3-Dec-11 17:46pm

Rate this:

## Solution 1

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.

```#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!

Top Experts
Last 24hrsThis month
 Graeme_Grant 335 ppolymorphe 241 Tadit Dash (ତଡିତ୍ କୁମାର ଦାଶ) 150 Maciej Los 140 Jochen Arndt 126
 OriginalGriff 3,961 Peter Leow 2,901 Karthik Bangalore 2,350 ppolymorphe 2,303 Richard MacCutchan 1,554