Priority Queue Decrease Key function used in Dijkstra's Algorithm

See more:

algorithm

Hi! I have a question on how to do a decrease key function for a minimum priority queue implemented by a heap, as well as a unsorted list. I need this function for use in a Dijkstra's algorithm. The function is as follows:

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.

Either implementation will work, and I have these functions working for both implementations: size(), empty(), insert(), minElement(), minKey(). The code will work if I take away anything related to the hash function. I have the idea for the heap implementation and I only have one line of code that I can't figure out. I am trying to use a map in the Binary heap to connect the Locator* with the ElemType. This line of code:

typedef map<elemtype,> hash;

but I cannot figure out why it will not work. Also, if I can get help on the unsorted list implementation, I will be very grateful.

I have tried using an iterator for the list implementation, and I have tried accessing the setKey() function from Item.h, and I thought I might be able to make a new element from the position, change the key, and delete the old element in exchange with the new element. None of these ideas have worked. Any help will be much appreciated.

My code...

This is my Item.h file which can be considered 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.

#include <map>

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;
	}
};

This is the binary heap 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.

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);
}

This is the list that the priority queue is implemented from. You can change out the List and the Heap, but must change the includes around.

#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 "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);
    }
};

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> pqHeap; //Priority Queue Heap with String
	string elem;
	elem = "bdd";
	pqHeap.insertItem(9, elem);
	elem = "acd";
	pqHeap.insertItem(7, elem);
	elem = "bcd";
	pqHeap.insertItem(8, elem);

	cout << "minElement: " << pqHeap.minElement() << endl;
	cout << "minKey: " << pqHeap.minKey() << endl;

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

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

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

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

	return 0;
}

It all compiles right now if the decreaseKey function is removed and the hash map is removed 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!