本地有序集或优先级队列的实现？

Question

我有一个相当大的对象集来表示数字，我想根据自定义的顺序选择这些数字。这种排序包括几个标准，例如它们表示的类型(一些数字用一个区间表示)，它们的完整性和最终的值。这些数字在整个程序中都是共享的(共享指针)，对此我无能为力。

但是，元素属性可以随时更改，这样顺序就会更改，而我无法通知容器这一点。例如，一些操作需要对由间隔表示的数字进行细化，在此细化过程中，可以找到确切的值。因此，数字从区间表示变为有理数，甚至可能是整数。由于共享实例的原因，这种更改会立即传播到容器中的编号，并打破顺序(我甚至不知道哪个编号发生了更改)。这完全破坏了std::set。

所以我想要的是一个容器，它试图被排序，但不依赖于此。只要操作检测到不正确的排序，就应该在本地更正此排序。例如，insert将插入元素(使用二进制搜索)，并始终检查当前元素的顺序(w.r.t.邻居)是正确的。

我愿意接受“给我最小的元素”就是“给我一个小元素”，find或remove会有线性复杂度:我只需要front，insert和remove_front就特别有效。

有没有这样的实现呢？您将如何实现这一点？

Answer 1

如果你正在寻找标准库中的算法，你应该看看：

std::make_heap
std::pop_heap
std::push_heap

在中。它们可能会满足您的需求，即使它们不能满足您的需求，我也非常肯定您会在某种堆结构中找到您想要的东西。哪一个可能取决于你的代码是如何构造的，以及你期望一个值改变的频率等。

简而言之：

堆是一种快速查找和提取最小(或最大)元素的数据结构。对于大多数堆来说，在线性时间或更短的时间内创建、重构堆也是可能的。如果您想了解更多关于堆的知识，可以从this page on Wikipedia开始。