c++ - 在 C++ 中有效地管理数组二进制堆的句柄？

Question

有没有一种方法可以有效地跟踪数组二进制堆中的句柄？

由于传统二叉堆中没有内置快速查找功能，用户需要一个 'handle_type' 来对堆中的任意元素进行 delete 或 decrease_key。

您不能在数组中使用指针或索引，因为堆操作会移动元素的位置。我想不出像传统堆实现那样仅使用类堆栈结构的简单解决方案。否则，我将不得不使用“新建/删除”，但感觉效率很低。

我不想对过早的优化过于着迷，但我希望它成为我的标准实用程序库的一部分，所以我想付出一点努力来了解什么被认为是此类事情的最佳实践。

也许只是使用“新建/删除”的天真的实现是去这里的方式。但如果可以的话，我想先从比我聪明的人那里得到一些建议。

C++ 标准库中的优先级队列实现似乎完全通过不支持“decrease_key”操作来回避这个问题。我一直在翻阅 CLRS，他们提到了这个问题，但并没有真正讨论它:

we shall not pursue them here, other than noting that... these handles do need to be correctly maintained.

这里有我忽略的简单方法吗？ 当“严肃的”库需要一个需要“decrease_key”操作的通用数组堆时，它们会做什么？

Answer 1

Is there a way to efficiently keep track of handles in an array binary tree?

这在假设上是可能的(但不是很漂亮)。在内部，数据结构不是存储元素数组，而是存储指向包含一对索引和元素的结构的指针(或智能指针)数组。

1. 当一个元素首次插入到数组中的位置 i 时，数据结构会将此结构的索引初始化为 i。

2. 随着数据结构在数组中移动元素，它应该修改索引以反射(reflect)新位置。

push 的结果可以是指向此结构的指针(可能包装在不透明类中)。为了访问特定元素(例如，对于 decrease_key)，您将使用此返回值调用堆的某些方法。然后堆将

1. 知道数组的地址(毕竟它是它的成员)
2. 通过您刚刚发送的结构了解数组中的索引。

例如，它可以因此实现 decrease_key。

---

但是，可能有更好(并且更简单)的解决方案。请注意，上述解决方案不会改变数组堆的渐近复杂性，但常量会更糟。相反，如果你看这个summary of heap running times ，您可以看到二叉堆对于 decrease_key 操作并没有很好的性能。如果需要，最好使用 Fibonnacci 堆(或其他一些数据结构)。这就引出了你的最后一个问题

What do "serious" libraries do when they need a general purpose array heap that needs a 'decrease_key' operation?

库，例如 boost::heap通常确实会实现更适合更高级操作的其他数据结构(例如，decrease_key)。这些数据结构自然是基于节点的，并且自然支持不像数组那样容易失效的返回值。