Sunday, July 1, 2012

Binary heap based priority queue in Qt

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


2 comments:

  1. Thanks for the exemplary code. However I think there is a bug wrt the case
    [code]
    if( right > count() - 1) {
    break;
    }
    [/code]
    because a priorization with the left child is omitted but necessary.

    Regards,
    M.Akron

    ReplyDelete
  2. Hi M.Akron, Thank you for feedback.

    ReplyDelete