优先队列减少键功能 [英] Priority Queue Decrease Key Function
问题描述
嗨！我正在尝试为Dijkstra算法中使用的Priority Queue实现减少键功能.我是这个网站的新手，但是如果需要，我可以上传我的源文件.我需要知道如何仅对未排序的列表和堆执行此功能.谢谢！
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!
推荐答案
好的，抱歉.仍然对此习以为常.这是我的Item.h文件，可以将其视为树的节点".实际的节点"存储在(最小)优先级队列列表中(未排序).还包含定位器功能.
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;
}
};
这是实现优先级队列的未排序列表.我需要帮助的功能是我要接受int以确定应该更改哪个位置以及将其更改为的键的reduceKey函数.其余的工作.
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) {
}
}
这是带有比较器功能的实际优先级队列文件，可以从>"更改为(最小)到<" (最大).
函数decKey应该从list.h调用reduceKey并传递我上面提到的项(键和位置).
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);
}
};
而main.cpp文件只是一个普通的主文件，没什么特别的.
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;
}
现在所有这些都可以编译，而我唯一尚未实现的就是我要实现Dijkstra算法所需的减少键功能.感谢您提供的所有帮助，如果我以错误的方式处理此问题，我们深表歉意.谢谢您能给我的帮助！
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!
这篇关于优先队列减少键功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
