7
\$\begingroup\$

Here I have implemented a priority queue, with the addition of the raise_priority (also known as reduce key) operation. The reason I have effectively reimplemented std::priority_queue is because the STL implementation does not have a raise_priority operation, nor can it be implemented (No access to the underlying container). That being said, the part I am mostly concerned about in terms of performance is the raise_priority operation.

template<typename K, typename T, typename C = std::less<K>>
    requires std::predicate<C, K, K>
class PriorityVectorQueue {
    std::vector<std::pair<K, T>> heap;
private:
    inline void bubble(size_t index) {
        while (index > 0 && C()(heap[(index - 1) / 2].first, heap[index].first)) {
            std::swap(heap[index], heap[(index - 1) / 2]);
            index = (index - 1) / 2;
        }
    }
    
    inline void sink(size_t index) {
        size_t size = heap.size();
        while (2 * index + 1 < size) {
            size_t child = 2 * index + 1;

            if (child + 1 < size && C()(heap[child].first, heap[child + 1].first)) {
                ++child;
            }

            if (C()(heap[index].first, heap[child].first)) {
                std::swap(heap[index], heap[child]);
                index = child;
            } else {
                break;
            }
        }
    }
public:
    inline PriorityVectorQueue() : heap() {

    };
    /**
     * @brief Insert a new element into the PriorityQueue
    */
    inline void insert(K key, T elem) {
        heap.emplace_back(key, elem);
        bubble(heap.size() - 1);
    };
    /**
     * @brief Construct a new element from the given arguments in the PriorityQueue
    */
    template<typename... Args>
        requires std::constructible_from<T, Args...>
    inline void emplace(K key, Args&&... args) {
        // Should I be forwarding the key as a tuple?
        heap.emplace_back(std::piecewise_construct, std::forward_as_tuple(key), std::forward_as_tuple(args...));
        bubble(heap.size() - 1);
    }

    /**
     * @brief Access the top element from the PriorityQueue
    */
    inline const T& top() const {
        return heap.front().second;
    }

    /**
     * @brief Remove the top element from the PriorityQueue
    */
    inline void pop() {
        heap.front() = heap.back();
        heap.pop_back();
        sink(0);
    }

    /**
     * @brief Re-key a previously inserted key into the 
    */
    template<typename I = std::equal_to<T>>
        requires std::predicate<I, T, T>
    inline void raise_priority(K new_key, T value) {
        // TODO: Is there a better way to do this?
        auto it = std::find_if(heap.cbegin(), heap.cend(), [&value](const auto& entry) {
            return I()(entry.second, value);
        });

        if (it != heap.cend()) {
            size_t index = std::distance(heap.cbegin(), it);
            heap[index].first = new_key;
            
            bubble(index);
        }
    }

    template<typename I, typename... Args>
        requires std::predicate<I, T, Args...> && std::constructible_from<T, Args...>
    inline void raise_priority(K new_key, Args&&... args) {
        // TODO: Is there a better way to do this?
        auto it = std::find_if(heap.cbegin(), heap.cend(), [&args...](const auto& entry) {
            return I()(entry.second, std::forward<Args>(args)...);
        });

        if (it != heap.cend()) {
            size_t index = std::distance(heap.cbegin(), it);
            heap[index].first = new_key;
            
            bubble(index);
        }
    }

    template<typename I, typename... Args>
        requires std::predicate<I, T, T> && std::constructible_from<T, Args...>
    inline void raise_priority(K new_key, Args&&... args) {
        raise_priority<I>(new_key, { std::forward<Args>(args)... });
    }
    
    inline bool empty() const {
        return heap.empty();
    }
};
```
\$\endgroup\$
1

2 Answers 2

Reset to default
4
+100
\$\begingroup\$

It's not a drop-in replacement

The reason I have effectively reimplemented std::priority_queue is because the STL implementation does not have a raise_priority operation

But in the process you have changed the interface in other ways. It would be nicer if it was a drop-in replacement for std::priority_queue with just the added raise_priority() member function (and perhaps add a lower_priority() as well).

First, add a template parameter Container, so the user can use something other than std::vector if so desired. You might want to add a requires clause that this Container supports random access and has push_back() and related member functions.

Second, don't store key/value pairs in the container, but just T, and remove K. C (which I would rename to Compare for clarity) should then work on Ts. Note that the caller can always set T to be a std::pair<Key, Value>, and pass a Compare that just compares the Key part, but now it's no longer the responsibility of your class. The same goes for I (which I would rename to Equal), which the caller can set to just compare the Value part if so desired.

The only issue with this is if you want to do better than \$O(N)\$ to find an entry in the queue. harold suggested using a std::unordered_map to get \$O(1)\$ lookups. This might require passing a custom hash function and equality comparison function for the map to index on the value part.

Member functions missing are: push() (you have insert(), but it doesn't have an overload for r-value references), size(), swap(), and soon also push_range().

What about duplicate values?

Consider pushing two elements with the same value to the queue:

PriorityVectorQueue<int, std::string> queue;
queue.emplace(1, "foo");
queue.emplace(2, "foo");

This is perfectly fine for most of the functionality of your priority queue. However, if you want to raise the priority of one of them, you have a problem: the call to std::find_if() will just find the first entry in the heap and change the priority of that one. Note that depending on what other elements are in the queue, there is no guarantee at all which key the one it will pick has!

Maybe the caller really wants to allow duplicate values, but it also knows the exact key/value pair it wants to raise the priority of. However, your interface does not allow it to specify that. If you don't explicitly store a std::pair<K, T> to begin with, your class won't have that issue.

Unnecessary use of inline

There is no need to mark member functions inline if they are defined inside the class declaration, they will then already be implicitly inline.

No need to add an explicit constructor

heap should have a default constructor, so there is no need to explicitly construct it yourself. Since that was the only thing your constructor did, you can completely remove it.

Incomplete Doxygen documentation

You added some comments that look like they are in the Doxygen format. However, several member functions are missing comments completely, and none of them have any @param and/or @return descriptions. If you want to do this properly, you should add all of that. Run the Doxygen tools with warnings enabled on your source, and fix all the warnings it reports.

Consider using std::push_heap() and std::pop_heap()

You implemented your own bubble() and sink() operations to maintain the heap property, but the standard library comes with std::push_heap() and std::pop_heap() that you could have used.

\$\endgroup\$
5
  • \$\begingroup\$ Duplicate values were not accounted for. They realistically shouldn't exist - it makes no sense to have the same value in the queue but with multiple different priorities. \$\endgroup\$ Commented Jun 16, 2023 at 3:08
  • \$\begingroup\$ I'll have to disagree. Consider a queue of notes to play on an instrument. The key in the queue is the time the note has to be played, the value is the pitch. Most songs have the same pitch note played multiple times. Maybe you can say that the time should then also be part of the value, but then you'd have some duplicate information in each entry in your priority queue. \$\endgroup\$ Commented Jun 16, 2023 at 6:55
  • 1
    \$\begingroup\$ That's a queue, not a priority queue. \$\endgroup\$ Commented Jun 16, 2023 at 14:40
  • \$\begingroup\$ Some variants of A* end up with differently-weighted duplicates in their priority queue - but not the variant that modifies the keys since that's done to prevent the duplicates in the first place. I'm not sure which side of the argument that example falls on but it's something \$\endgroup\$ Commented Jun 16, 2023 at 18:51
  • \$\begingroup\$ On Linux, the /dev/snd/seq device can be used to prepare MIDI notes to be sent to devices. A non-real-time userspace process can say "please play this note at this time", and the kernel can then, using high resolution timers, ensure the notes are sent at precisely the right time. Multiple programs can open /dev/snd/seq and schedule notes to be sent to the same device. This could be implemented using a priority queue, and I don't think this is a very contrived example. Sure, there are other ways to do it, but I wouldn't say that the concept of a priority queue excludes identical values. \$\endgroup\$ Commented Jun 16, 2023 at 21:17
4
\$\begingroup\$

Finding an element

    // TODO: Is there a better way to do this?
    auto it = std::find_if(heap.cbegin(), heap.cend(), [&value](const auto& entry) {
        return I()(entry.second, value);
    });

A technique that can be used for this is maintaining an unordered_map (or a different kind of map if you prefer) from value ("backwards key" essentially, since this whole scheme of identifying a heap item by its value requires it to be unique) to its index in the underlying vector.

This adds some overhead to bubble and sink, but it's a constant factor: just writing new values into the map every time an item is moved, so the number of extra operations is proportional to the number of operations that already happened anyway. It's not a constant amount extra, it's a constant factor.

Obviously it adds some size overhead as well. Then in raise_priority, you can look up the index of the item by its value in constant time, but whether that is actually worth it depends on the circumstances.

By the way raise_priority currently does not guarantee that the priority is raised, it will accept any new key and then only call bubble. Putting in a bad key that lowers the priority would break the internal structure of the heap. That only happens if the interface is abused to do something that isn't supposed to be done, but it's still bad manners for a data structure to become internally inconsistent. It wouldn't be very expensive to allow lowering a priority as well (by calling either bubble or sink as necessary).

swap-based bubble and sink

Basing bubble and sink on std::swap gets the job done, but with almost twice as many writes as is really necessary. Alternatively, you can move an element out of the heap, do a bunch of moves instead of swaps, and then move the element that was "off to the side" into the heap in its final position.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Updating the map in bubble/sink is not a constant factor, its maximum complexity is logarithmic on the size of the heap. \$\endgroup\$ Commented Jun 15, 2023 at 19:56
  • \$\begingroup\$ @AriaHarper the number of operations that gets added is similar to the number of operations that already happens. In an abuse of notation, O(log n) + O(log n) = O(log n). The only thing that changes is the constant factor. It doesn't become O((log n)²). \$\endgroup\$ Commented Jun 15, 2023 at 20:02
  • \$\begingroup\$ Or to put it another way, the loop runs log n times, and has constant number of operations per iteration. It doesn't matter what that constant is, the whole thing is always O(log n). \$\endgroup\$ Commented Jun 15, 2023 at 20:06
  • \$\begingroup\$ If we do N insert operations, the complexity required to maintain the map will be approximately N log(N), with a constant complexity to find the index for a value. If we search linearly for a value to find its index, a complexity of N is required. As long as fewer than log(N) rekey operations are performed, it's optimal to search the heap linearly. \$\endgroup\$ Commented Jun 15, 2023 at 20:12
  • \$\begingroup\$ @AriaHarper OK that's a different kind of argument, and I don't think it makes sense to make it in that way because the threshold at which it's going to be worth it or not depends on all of the constants involved, which the only way to find out is to actually measure it in real life. I expect that in real life, linear search stays pretty good for pretty long, since computers are really good at that sort of thing (and not so much at randomly accessing a hashmap). One "unit" of linear searching is not equivalent to one "unit" of updating indices in a hashmap \$\endgroup\$ Commented Jun 15, 2023 at 20:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.