C++中基于pairing heaps实现带自动递增优先级的优先队列问题

Great question! Dealing with time-based priority increments in pairing heaps is tricky because traversing the entire heap to update elements is inefficient. Luckily, there are two practical approaches to solve this without full heap traversal—let’s dive into them:

Approach 1: Dynamic Priority Calculation (No Heap Modifications) #

Instead of storing a fixed priority value, compute the element’s current priority on-the-fly using its insertion timestamp and base priority. This avoids modifying the heap structure entirely.

How it works: #

• Each element stores its base priority and the timestamp when it was inserted into the heap.
• When comparing elements (for maintaining the pairing heap’s order), calculate the current priority by adding time-based increments to the base value. For example:
  • If the element has been in the heap for ≥5 minutes, add your desired priority boost.
  • Otherwise, use the base priority.

Code Example: #

First, define your element class with timestamp tracking:

#include <chrono>

class MyElement {
public:
    int data; // Your custom data
    int base_priority;
    std::chrono::steady_clock::time_point insert_time;

    MyElement(int d, int bp) 
        : data(d), base_priority(bp), insert_time(std::chrono::steady_clock::now()) {}
};

Then, create a custom comparator for your pairing heap that calculates real-time priority:

struct DynamicPriorityCompare {
    bool operator()(const MyElement* a, const MyElement* b) const {
        auto now = std::chrono::steady_clock::now();
        // Calculate current priority for element a
        int a_current_prio = a->base_priority;
        auto time_in_heap = std::chrono::duration_cast<std::chrono::minutes>(now - a->insert_time);
        if (time_in_heap.count() >= 5) {
            a_current_prio += 10; // Boost priority by 10 after 5 minutes
        }
        // Calculate current priority for element b
        int b_current_prio = b->base_priority;
        time_in_heap = std::chrono::duration_cast<std::chrono::minutes>(now - b->insert_time);
        if (time_in_heap.count() >= 5) {
            b_current_prio += 10;
        }
        // For a max-heap: return true if a should come after b (lower priority)
        return a_current_prio < b_current_prio;
    }
};

Caveats: #

• This works best if priorities are monotonically increasing (they never decrease over time).
• The heap structure may become "stale"—an element with a now-higher priority might be buried deeper in the heap, and you won’t know until you pop elements. This is a tradeoff for avoiding heap modifications.

Approach 2: Event-Driven Lazy Updates (Guarantees Correct Heap Order) #

This method uses an event queue to track when elements need priority boosts, then updates the pairing heap only for elements whose boost time has arrived. Pairing heaps support efficient increase-key operations (amortized O(1) time), making this approach reliable.

How it works: #

1. When inserting an element into the main pairing heap, create an event for its priority boost (insert time + 5 minutes) and add it to a sorted event queue.
2. Before any operation on the main heap (e.g., top(), pop()), process all expired events:
   • For each event, update the element’s priority.
   • Call the pairing heap’s increase-key method to reposition the element in the heap.
3. The event queue is a min-heap sorted by trigger time, so we always process the earliest expired events first.

Code Example: #

First, define an event structure and update the element class to track if it’s been boosted:

#include <memory>
#include <queue>
#include <unordered_map>

class MyElement {
public:
    int data;
    int base_priority;
    std::chrono::steady_clock::time_point insert_time;
    bool is_boosted = false;

    MyElement(int d, int bp) 
        : data(d), base_priority(bp), insert_time(std::chrono::steady_clock::now()) {}
};

struct PriorityBoostEvent {
    std::chrono::steady_clock::time_point trigger_time;
    std::weak_ptr<MyElement> element; // Use weak_ptr to avoid dangling pointers
    int boost_amount;

    // Min-heap comparator: earliest events come first
    bool operator>(const PriorityBoostEvent& other) const {
        return trigger_time > other.trigger_time;
    }
};

Next, implement a pairing heap with increase-key support (simplified version):

template <typename T, typename Compare>
struct PairingHeapNode {
    T data;
    PairingHeapNode* child = nullptr;
    PairingHeapNode* sibling = nullptr;
    PairingHeapNode* parent = nullptr;

    PairingHeapNode(T d) : data(d) {}
};

template <typename T, typename Compare>
class PairingHeap {
private:
    PairingHeapNode<T, Compare>* root = nullptr;
    Compare comp;

    PairingHeapNode<T, Compare>* merge(PairingHeapNode<T, Compare>* a, PairingHeapNode<T, Compare>* b) {
        if (!a) return b;
        if (!b) return a;
        if (comp(a->data, b->data)) {
            a->parent = b;
            a->sibling = b->child;
            b->child = a;
            return b;
        } else {
            b->parent = a;
            b->sibling = a->child;
            a->child = b;
            return a;
        }
    }

    PairingHeapNode<T, Compare>* merge_siblings(PairingHeapNode<T, Compare>* node) {
        if (!node || !node->sibling) return node;
        auto next = node->sibling;
        auto rest = next->sibling;
        node->sibling = nullptr;
        next->sibling = nullptr;
        return merge(merge(node, next), merge_siblings(rest));
    }

public:
    PairingHeapNode<T, Compare>* push(T data) {
        auto new_node = new PairingHeapNode<T, Compare>(data);
        root = merge(root, new_node);
        return new_node;
    }

    T top() const { return root->data; }

    void pop() {
        if (!root) return;
        auto old_root = root;
        root = merge_siblings(root->child);
        delete old_root;
    }

    void increase_key(PairingHeapNode<T, Compare>* node) {
        if (node == root) return;
        // Remove node from parent's child list
        if (node->parent->child == node) {
            node->parent->child = node->sibling;
        } else {
            auto sibling = node->parent->child;
            while (sibling->sibling != node) sibling = sibling->sibling;
            sibling->sibling = node->sibling;
        }
        node->parent = nullptr;
        node->sibling = nullptr;
        // Merge node back into the root
        root = merge(root, node);
    }

    bool empty() const { return root == nullptr; }
};

Finally, implement the event processing logic and integrate everything:

// Helper to process expired priority boost events
void process_expired_events(
    std::priority_queue<PriorityBoostEvent, std::vector<PriorityBoostEvent>, std::greater<>>& event_queue,
    PairingHeap<std::shared_ptr<MyElement>, DynamicPriorityCompare>& main_heap,
    std::unordered_map<std::shared_ptr<MyElement>, PairingHeapNode<std::shared_ptr<MyElement>, DynamicPriorityCompare>*>& node_map
) {
    auto now = std::chrono::steady_clock::now();
    while (!event_queue.empty()) {
        const auto& top_event = event_queue.top();
        if (top_event.trigger_time > now) break;

        // Check if the element still exists in the main heap
        if (auto elem_ptr = top_event.element.lock()) {
            if (!elem_ptr->is_boosted) {
                elem_ptr->base_priority += top_event.boost_amount;
                elem_ptr->is_boosted = true;
                // Update the element's position in the pairing heap
                auto node_it = node_map.find(elem_ptr);
                if (node_it != node_map.end()) {
                    main_heap.increase_key(node_it->second);
                }
            }
        }
        event_queue.pop();
    }
}

// Example usage
int main() {
    PairingHeap<std::shared_ptr<MyElement>, DynamicPriorityCompare> main_heap;
    std::priority_queue<PriorityBoostEvent, std::vector<PriorityBoostEvent>, std::greater<>> event_queue;
    std::unordered_map<std::shared_ptr<MyElement>, PairingHeapNode<std::shared_ptr<MyElement>, DynamicPriorityCompare>*> node_map;

    // Insert an element
    auto elem = std::make_shared<MyElement>(42, 5);
    auto node = main_heap.push(elem);
    node_map[elem] = node;

    // Create a priority boost event (5 minutes from insertion)
    PriorityBoostEvent event;
    event.trigger_time = elem->insert_time + std::chrono::minutes(5);
    event.element = elem;
    event.boost_amount = 10;
    event_queue.push(event);

    // Before accessing the main heap, process expired events
    process_expired_events(event_queue, main_heap, node_map);

    // Now we can safely get the top element with up-to-date priority
    auto top_elem = main_heap.top();
    return 0;
}

Why this works: #

• We only modify elements that have reached their boost time, avoiding full heap traversal.
• The increase-key operation in pairing heaps efficiently reorders the heap to maintain correct priority order.
• Using weak_ptr prevents dangling pointers if elements are popped from the main heap before their event triggers.

内容的提问来源于stack exchange，提问作者Noname