Long time ago, I posted implementation of Priority Queue implemented using Qt's
QQueue data structure. Here is old post.
That code was offering o(n) performance for enqueue operation and o(1) performance for dequeue operation. This might be acceptable for small data set. But for large data set you might want to use Priority queue based on Binary heap implementation.
I tried to implement my old priority queue using Binary heap, here is my implementation.
Following code implements BinaryHeap using QList. BinaryHeap class implements enqueue, dequeue and count method.
And based on above BinaryHeap class, following is my PriorityQueue class.
QQueue data structure. Here is old post.
That code was offering o(n) performance for enqueue operation and o(1) performance for dequeue operation. This might be acceptable for small data set. But for large data set you might want to use Priority queue based on Binary heap implementation.
I tried to implement my old priority queue using Binary heap, here is my implementation.
Following code implements BinaryHeap using QList. BinaryHeap class implements enqueue, dequeue and count method.
template <class T>
class BinaryHeap {
public:
void enqueue(T item) {
mList.append(item);
int i = mList.count() - 1;
int parent = (i-1)/2;
while( parent >= 0 && mList[i] < mList[parent] ) {
T temp = mList[parent];
mList[parent] = mList[i];
mList[i] = temp;
i = parent;
parent = (i-1)/2;
}
}
T dequeue() {
if( mList.isEmpty()) {
return T();
}
T item = mList[0];
int i = 0;
mList[0] = mList[ count()-1];
mList.removeLast();
while( i < count() ) {
int left = 2*i+1;
int right = left + 1;
if( right > count() - 1) {
break;
}
int min = left;
if( mList[right] < mList[left] ) {
min = right;
}
if( mList[i] > mList[min] ) {
T data = mList[min];
mList[min] = mList[i];
mList[i] = data;
i = min;
} else {
break;
}
}
return item;
}
int count() const {
return mList.count();
}
private:
QList<T> mList;
};
And based on above BinaryHeap class, following is my PriorityQueue class.
enum Priority {
Low = 2,
Normal = 1,
High = 0
};
template <class T>
class PriorityQueue
{
public:
void enqueue( Priority priority, T data) {
Item item(priority,data);
mHeap.enqueue(item);
}
T dequeue() {
Item item = mHeap.dequeue();
return item.mData;
}
int count() const {
return mHeap.count();
}
private:
BinaryHeap<Item> mHeap;
};
And Item class looks like below.
class Item{
public:
Item() {
}
Item(Priority priority, T data ):
mPriority(priority),mData(data)
{}
bool operator<(const Item& other) {
return mPriority < other.mPriority;
}
Priority mPriority;
T mData;
};
