Skip to main content
Notice removed Draw attention by Peilonrayz
Bounty Ended with G. Sliepen's answer chosen by Peilonrayz
Updated code since no answers were posted yet.
Source Link
FreezePhoenix
  • 1.3k
  • 1
  • 12
  • 27
template<typename TK, typename C = std::less<T>T, typename IC = std::equal_to<T>>less<K>>
    requires std::predicate<C, T, T>&& std::predicate<I, TK, T>K>
class PriorityVectorQueue {
    std::vector<T>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(constK T&key, T elem) {
        heap.push_backemplace_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::forward<Args>piecewise_construct, std::forward_as_tuple(argskey), 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;
    }

    inline/**
 void pop() {
  * @brief Remove the top element from the PriorityQueue
 /   */ 
 TODO: More efficient algorithm?inline void pop() {
        std::pop_heap(heap.beginfront(), = heap.end(), Cback());
        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(TK new_key, T value) {
        // TODO: Is there a better way to do this?
        auto it = std::find_if(heap.cbegin(), heap.cend(), [&new_key][&value](const T&auto& elemententry) {
            return I()(elemententry.second, new_keyvalue);
        });

        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) {
        // WeTODO: don'tIs reallythere needa better way to do this?
 overload       auto it = std::find_if(heap.cbegin(), butheap.cend(), having[&args...](const auto& entry) {
            return I()(entry.second, std::forward<Args>(args)...);
        });

        if (it makes!= youheap.cend()) able{
 to use          size_t index = std::distance(heap.cbegin(), it);
 consistently with `emplace`         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();
    }
};
```
template<typename T, typename C = std::less<T>, typename I = std::equal_to<T>>
    requires std::predicate<C, T, T>&& std::predicate<I, T, T>
class PriorityVectorQueue {
    std::vector<T> heap;
private:
    inline void bubble(size_t index) {
        while (index > 0 && C()(heap[(index - 1) / 2], heap[index])) {
            std::swap(heap[index], heap[(index - 1) / 2]);
            index = (index - 1) / 2;
        }
    }
public:
    inline PriorityVectorQueue() : heap() {

    };
    inline void insert(const T& elem) {
        heap.push_back(elem);
        bubble(heap.size() - 1);
    };
    template<typename... Args>
        requires std::constructible_from<T, Args...>
    inline void emplace(Args&&... args) {
        heap.emplace_back(std::forward<Args>(args)...);
        bubble(heap.size() - 1);
    }

    inline const T& top() const {
        return heap.front();
    }

    inline void pop() {
        // TODO: More efficient algorithm?
        std::pop_heap(heap.begin(), heap.end(), C());
        heap.pop_back();
    }

    inline void raise_priority(T new_key) {
        // TODO: Is there a better way to do this?
        auto it = std::find_if(heap.cbegin(), heap.cend(), [&new_key](const T& element) {
            return I()(element, new_key);
        });

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

    template<typename... Args>
        requires std::constructible_from<T, Args...>
    inline void raise_priority(Args&&... args) {
        // We don't really need this overload, but having it makes you able to use it consistently with `emplace`
        raise_priority({ std::forward<Args>(args)... });
    }
    inline bool empty() const {
        return heap.empty();
    }
};
```
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();
    }
};
```
Notice added Draw attention by Peilonrayz
Bounty Started worth 100 reputation by Peilonrayz
Source Link
FreezePhoenix
  • 1.3k
  • 1
  • 12
  • 27

Priority Queue (With raise priority operation) using Vector

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 T, typename C = std::less<T>, typename I = std::equal_to<T>>
    requires std::predicate<C, T, T>&& std::predicate<I, T, T>
class PriorityVectorQueue {
    std::vector<T> heap;
private:
    inline void bubble(size_t index) {
        while (index > 0 && C()(heap[(index - 1) / 2], heap[index])) {
            std::swap(heap[index], heap[(index - 1) / 2]);
            index = (index - 1) / 2;
        }
    }
public:
    inline PriorityVectorQueue() : heap() {

    };
    inline void insert(const T& elem) {
        heap.push_back(elem);
        bubble(heap.size() - 1);
    };
    template<typename... Args>
        requires std::constructible_from<T, Args...>
    inline void emplace(Args&&... args) {
        heap.emplace_back(std::forward<Args>(args)...);
        bubble(heap.size() - 1);
    }

    inline const T& top() const {
        return heap.front();
    }

    inline void pop() {
        // TODO: More efficient algorithm?
        std::pop_heap(heap.begin(), heap.end(), C());
        heap.pop_back();
    }

    inline void raise_priority(T new_key) {
        // TODO: Is there a better way to do this?
        auto it = std::find_if(heap.cbegin(), heap.cend(), [&new_key](const T& element) {
            return I()(element, new_key);
        });

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

    template<typename... Args>
        requires std::constructible_from<T, Args...>
    inline void raise_priority(Args&&... args) {
        // We don't really need this overload, but having it makes you able to use it consistently with `emplace`
        raise_priority({ std::forward<Args>(args)... });
    }
    inline bool empty() const {
        return heap.empty();
    }
};
```