问题描述
我使用优先级队列作为一个额外需求的调度程序。我需要能够取消预定的项目。这等于从优先级队列的中间删除一个项目。
我不能使用 std :: priority_queue
我试图使用算法
堆函数。但我仍然缺少我需要的一块。当我从堆的中间删除一个元素我希望它有效地重建自己。 C ++提供了这些堆函数:
-
std :: make_heap
O 3n) -
std :: push_heap
O(lg(n) li>
std :: pop_heap
O(2 lg(n))
我想要一个新的函数,如
std :: repair_heap
3n 。我会提供它的位置,在那里被取消的项目用于居住,它会适当调整堆。
这似乎是一个巨大的疏忽,提供
std :: repair_heap
函数。我有缺少一些明显的东西吗?
是否有库提供stl兼容
std :: repair_heap
p>
是否有更好的数据结构来建模调度程序?
注意:
由于几个原因,我没有使用std :: map
。
- 一个堆有恒定的内存开销。
- 一个堆具有真棒缓存区域性。
解决方案不幸的是,标准缺少这个(相当重要的)函数。使用g ++,你可以使用非标准函数
std :: __ adjust_heap
来做到这一点,但是没有简单的可移植的方法 - 和__adjust_heap
在不同版本的g ++中略有不同,所以你甚至不能在g ++版本上移植。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 anstd::map
for a few reasons.- A heap has constant memory overhead.
- A heap has awesome cache locality.
解决方案Unfortunately, the standard is missing this (fairly important) function. With g++, you can use the non-standard function
std::__adjust_heap
to do this, but there's no easy portable way of doing it -- and__adjust_heap
is slightly different in different versions of g++, so you can't even do it portably over g++ versions.这篇关于从std :: heap中间删除一个元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!