On 04/17/2015 12:12 PM, Berkay Elbir wrote:
Hello All,

I want to ask a question to you to be certain. Is void qsort() function
obsolete? Should we use std::sort instead of this function? Because I
have a priority list and need to sort it.

Slightly off-topic: Don't implement a priority queue this way. Unless you have a system where you get a bunch of those and can sort them once, and handle all of them. If this isn't the case, you are going to have inserts and removes mixed. Then you will continually sort something that's already sorted.

I have an old implementation of a priority queue you can use instead. It's an implementation of a binary heap algorithm. It's optimized for the case where there are just a few items in the queue and very rarely it will get a burst of more. If your case doesn't match this, you could probably remove the resize to minimum. You can instantiate it with anything that implements operator<.

I hope it helps.

Bo Thorsen,
Director, Viking Software.

--
Viking Software
Qt and C++ developers for hire
http://www.vikingsoft.eu
#ifndef VSTOOLS_PRIORITYQUEUE_H
#define VSTOOLS_PRIORITYQUEUE_H

#include <QList>

class PriorityQueueTest;

namespace VSTools {

template <typename T> class PriorityQueue {
public:
    enum { MinimumSpace = 8 };

    PriorityQueue() : mReserved(0), mCount(0), mEntries(0) {
    }

    ~PriorityQueue() {
        delete[] mEntries;
    }

    void enqueue(T item) {
        if (mCount < 2 && mReserved != MinimumSpace) {
            // Our list was (almost) empty, resize it to 8 so we have some room. This also prunes the list if it used to be bigger
            resize(MinimumSpace);
        } else if (mCount == mReserved) {
            // We need more space
            resize(mReserved * 4);
        }

        // Insert this at the end of the tree
        int i = mCount;
        int parent = (i - 1) / 2;
        mEntries[mCount++] = item;

        // Test that the tree is still in order
        while (parent >= 0 && i > 0 && mEntries[i] < mEntries[parent]) {
            swap(parent, i);

            // Go up the tree and retest
            i = parent;
            parent = (i - 1) / 2;
        }
    }

    T dequeue() {
        Q_ASSERT(!isEmpty());

        if (mCount == 1) {
            // Small optimization
            mCount = 0;
            return mEntries[0];
        }

        // Take the first and move the last to the top
        T item = mEntries[0];
        mEntries[0] = mEntries[--mCount];

        // Sink the top down
        int i = 0;
        while (true) {
            int swapWith = 2 * i + 1;

            if (swapWith >= mCount) {
                // We're at the end
                break;
            }

            if (swapWith < mCount - 1 && mEntries[swapWith + 1] < mEntries[swapWith]) {
                // Use the right entry instead
                ++swapWith;
            }

            if (mEntries[swapWith] < mEntries[i]) {
                swap(swapWith, i);
                i = swapWith;
            } else {
                // Done, we found the right place in the tree
                break;
            }
        }
        return item;
    }

    const T& peek() const {
        Q_ASSERT(!isEmpty());
        return mEntries[0];
    }

    inline int count() const { return mCount; }

    /// Returns true, if this queue is empty
    inline bool isEmpty() const { return mCount == 0; }

    void clear() {
        mCount = 0;
        if (mReserved > MinimumSpace) {
            resize(MinimumSpace);
        }
    }

private:
    Q_DISABLE_COPY(PriorityQueue)

    void resize(unsigned int reserved) {
        mReserved = reserved;
        T* oldEntries = mEntries;
        mEntries = new T[reserved];

        // Copy over the old entries
        for (int i=0; i<mCount; ++i) {
            mEntries[i] = oldEntries[i];
        }

        delete[] oldEntries;
    }

    inline void swap(int i, int j) {
        T temp = mEntries[i];
        mEntries[i] = mEntries[j];
        mEntries[j] = temp;
    }

    int mReserved;
    int mCount;
    T* mEntries;
};

}

#endif // PRIORITYQUEUE_H
_______________________________________________
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest

Reply via email to