从std :: heap中间删除一个元素 [英] Remove an element from the middle of an std::heap

问题描述

我使用优先级队列作为一个额外需求的调度程序。我需要能够取消预定的项目。这等于从优先级队列的中间删除一个项目。

我不能使用 std :: priority_queue

我试图使用算法堆函数。但我仍然缺少我需要的一块。当我从堆的中间删除一个元素我希望它有效地重建自己。 C ++提供了这些堆函数：

• std :: make_heap O 3n）


• std :: push_heap O（lg（n） li>
  
• std :: pop_heap O（2 lg（n））
/ ul>



我想要一个新的函数，如 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 an std::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中间删除一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！