13,201,934 members (71,289 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 16: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
 OriginalGriff 330 Richard MacCutchan 125 Dave Kreskowiak 100 ppolymorphe 75 GKP1992 75
 OriginalGriff 8,150 ppolymorphe 2,069 Karthik Bangalore 1,724 CPallini 1,208 Jochen Arndt 1,075