我正在尝试使用删除任何数字(不仅是最小值或最大值)的方法来实现我自己的堆，但我无法解决一个问题。要编写删除函数，我需要指向堆中元素的指针(以便删除给定元素的时间为 O(logn))。但是当我尝试这样做时:
vector<int*> ptr(n);
当然不行。
也许我应该在我的堆中插入另一个包含 int 的类或结构，但现在我想找到任何带有 int 的解决方案(因为我已经使用 int 实现了它)？
最佳答案
当您需要删除(或更改其优先级)除根以外的其他对象时，d 堆不一定是理想的数据结构:节点不断改变它们的位置，您需要跟踪各种移动。然而，这是可行的。要像这样使用堆，您需要返回一个句柄到新插入的对象，该对象标识某种保持不变的节点。由于 d-heap 算法依赖于树是一棵完美平衡的树，因此您实际上需要使用数组来实现它。由于这两个要求(使用数组和保留节点)是相互排斥的，因此您需要同时执行这两项操作，并从节点到数组有一个索引(这样您就可以找到对象在数组中的位置)和一个指针数组到节点(因此您可以在位置更改时更新节点)。几乎可以肯定你不想移动你的节点很多，即你宁愿接受通过搜索多个节点来找到移动节点的正确方向，即你想使用 d > 2。
有其他方法可以实现本质上基于节点的堆。特别是 Fibonacci 堆，它针对某些使用模式产生比通常的 O(ln(n)) 复杂性更好的摊销复杂性。但是，它们实现起来有些困难，只有当您需要频繁更改节点的优先级或您拥有相当大的数据集时，实际效率才会有所返回。
关于c++堆删除任何元素的方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8866871/