本文介绍了从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中间删除一个元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-05 19:49