I am designing a generic priority queue in C++ which can take any data type as key either it can be int or user defined structure. I want to implement priority queue using binary heap, linked lists, bionomial heap, and fibanocci heap. Here user can select any implementation. For some of the functions I should return internal handles to user so that users can pass to priority queue for certain operations to have good performance, for example change function, remove functions, here if we have handle we can have this implementations fast rather than searching.
So I have generic priority interface as shown below
template <class Item>
class IMyPriorityQueue {
private:
/* Implementattion dependent code
Here we can implement priority queue functions mentioned in public section of class using
ordered array, unordered array, ordered list, unordered list, heap data structure,
bionomial heap and fibonacci heap. (here list means double linked list).
Heap means is a tree is heap-ordered if the key in each node is larger than or equal to the keys in all of that node s children (if any).
Equivalently, the key in each node of a heap-ordered tree is smaller than or equal to the key in that node s parent (if any).
Read Robert Sedwick on various implementation have performance on Table 9.1 on page .
*/
public:
// Implementation-dependent handle definition
IMyPriorityQueue(int);
virtual ~IMyPriorityQueue();
virtual int empty() const = 0;
virtual handle insert(Item ) = 0;
virtual int getmax() = 0;
virtual void change(handle, Item) = 0;
virtual void remove(handle) = 0;
virtual void join(IMyPriorityQueue&) = 0;
};
template <class Item>
class CMyLinkedListPriorityQueue : public IMyPriorityQueue {
private:
// Implementing using unordered double linked list.
struct sPQNode {
Item pqItem;
sPQNode* pPrevPQNode;
sPQNode* pNextPQNode;
sPQNode(Item itm) {
pqItem = itm;
pPrevPQNode = 0;
pNextPQNode = 0;
}
};
// Note: here head and tail are it self sPQNode* rather than void* pointer which points to first node.
sPQNode* m_pPQhead;
sPQNode* m_pPQTail;
std::vector<sPQNode*> m_vecPQNodePointer;
int m_iVecContainerIndex;
CMyLinkedListPriorityQueue(int = 0) {
m_pPQhead = new sPQNode(0);
m_pPQTail = new sPQNode(0);
m_pPQhead->pPrevPQNode = m_pPQTail; m_pPQhead->pNextPQNode = m_pPQTail;
m_pPQTail->pPrevPQNode = m_pPQhead; m_pPQTail->pNextPQNode = m_pPQhead;
m_iVecContainerIndex = 0;
}
int empty() const {
return m_pPQhead->pNextPQNode->pNextPQNode == m_pPQhead;
m_iVecContainerIndex = 0;
}
handle insert(Item v) {
handle insPQNode = new node(v);
insPQNode->pNextPQNode = m_pPQhead->pNextPQNode; insPQNode->pNextPQNode->pPrevPQNode = insPQNode;
insPQNode->pPrevPQNode = m_pPQhead; m_pPQhead->pNextPQNode = insPQNode;
m_vecPQNodePointer[m_iVecContainerIndex++] = insPQNode
return (m_iVecContainerIndex - 1);
}
Item getmax() {
Item max; sPQNode* pHeadNext = head->next;
for (link t = x; t->next != head; t = t->next) {
if (x->item < t->item) x = t;
}
max = x->item;
remove(x);
return max;
}
void change(handle hItem, Item itm) {
m_iVecContainerIndex[hItem]->item = itm;
}
void remove(handle hItem) {
// **Question how to handle this and join operation**
}
void join(PQ<Item>& p) {
tail->prev->next = p.head->next;
p.head->next->prev = tail->prev;
head->prev = p.tail;
p.tail->next = head;
delete tail; delete p.head;
tail = p.tail;
}
};
Problem I am facing with above design if we remove an item and empty that particular location I am making that entry in vector to null, but problem is that vector size is growing as program runs for long time. I can think of use of map container but again this will search again. I want to avoid search during remove, join and change operations.
Any better design to handle above scenario.
Thanks for your inputs
