Edit Question - KnowledgeHub

Title Body

I'm using a priority queue as a scheduler with one extra requirement. I need to be able to cancel scheduled items. This equates to removing an item from the middle of the priority queue. I can't use std::priority_queue as access to any element other than top is protected. I'm trying to use the algorithm 's heap functions. But I'm still missing the piece I need. When I remove an element I from the middle of the heap I want it to rebuild itself efficiently. C++ provides these heap functions: std::make_heap O(3n) std::push_heap O(lg(n)) std::pop_heap O(2 lg(n)) I want a new function like std::repair_heap with a big-O < 3n . I'd provide it with location of the hole where the canceled item used to reside and it would properly adjust the heap. It seems to be a huge oversight to not to provide a std::repair_heap function. Am I missing something obvious? Is there library that provides an stl-compliant std::repair_heap ? Is there a better data structure for modeling a scheduler? NOTE : I'm not using an std::map for a few reasons. A heap has constant memory overhead. A heap has awesome cache locality.

Tags (comma-separated) Cancel