c++具有删除任何元素方法的堆
我正在尝试使用删除任何数字（不仅是最小值或最大值）的方法来实现我自己的堆，但我无法解决一个问题。要编写该删除函数，我需要指向堆中元素的指针（删除给定元素的时间为 O(logn)）。但是当我尝试这样做时：
vector<int*> ptr(n);
它当然不起作用。
也许我应该在堆中插入另一个包含 int 的类或结构，但现在我想找到任何包含 int 的解决方案（因为我已经使用 int 实现了它）？
I am trying to implement my own heap with the method removing any number (not only the min or max) but I can't solve one problem. To write that removing function I need the pointers to the elements in my heap (to have O(logn) time of removing given element). But when I have tried do it this way:
vector<int*> ptr(n);
it of course did not work.
Maybe I should insert into my heap another class or structure containing int, but for now I would like to find any solution with int (because I have already implemented it using int)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
当您需要删除根以外的其他对象（或更改其优先级）时，d 堆不一定是理想的数据结构：节点不断改变其位置，您需要跟踪各种移动。然而，这是可行的。要使用这样的堆，您将返回新插入对象的句柄，该句柄标识某种保持不变的节点。由于 d 堆算法依赖于完全平衡的树，因此您实际上需要使用数组来实现它。由于这两个要求（使用数组和让节点保持原样）是互斥的，因此您需要同时执行这两个要求，并拥有从节点到数组的索引（这样您就可以找到对象在数组中的位置）和一个来自数组到节点（这样你就可以在位置改变时更新节点）。几乎可以肯定，您不想太多地移动节点，即您宁愿接受通过搜索多个节点来找到移动节点的正确方向，即您想使用 ad > 。 2.
还有其他方法来实现本质上基于节点的堆。特别是斐波那契堆，它对于某些使用模式产生比通常的 O(ln(n)) 复杂度更好的摊销复杂度。然而，它们实施起来有些困难，并且只有当您需要频繁更改节点的优先级或者您有相当大的数据集时，实际效率才会得到回报。
When you need to remove (or change the priority of) other objects than the root, a d-heap isn't necessarily the ideal data structure: the nodes keep changing their position and you need to keep track of various moves. It is doable, however. To use a heap like this you would return a handle to the newly inserted object which identifies some sort of node which stays put. Since the d-heap algorithm relies on the tree being a perfectly balanced tree, you effectively need to implement it using an array. Since these two requirements (using an array and having nodes stay put) are mutually exclusive you need to do both and have an index from the nodes into the array (so you can find the position of the object in the array) and a pointer from the array to the node (so you can update the node when the position changes). Almost certainly you don't want to move your nodes a lot, i.e. you rather accept finding the proper direction to move a nodes by searching multiple nodes, i.e. you want to use a d > 2.
There are alternative approach to implement a heap which are inherently nodes based. In particular Fibonacci heaps which yield for certain usage patterns a better amortized complexity than the usual O(ln(n)) complexity. However, they are somewhat harder to implement and the actual efficiency only pays off if you either need to change the priority of a node frequently or you have fairly large data sets.
堆是一种特殊的数据结构；元素存储在二叉树中，并且有完善的添加或删除元素的过程。许多实现使用数组来保存树节点，并删除涉及移动 log(n) 个元素的元素。通常，按照数组的使用方式，数组位置 n 处的节点的子节点存储在位置 2n 和 2n+1 处；元素 0 留空。
这个维基百科页面很好地解释了算法。
A heap is a particular sort of data structure; the elements are stored in a binary tree, and there are well-established procedures for adding or removing elements. Many implementations use an array to hold the tree nodes, and removing an element involved moving log(n) elements around. Normally the way the array is used, the children of the node at array location n are stored at locations 2n and 2n+1; element 0 is left empty.
This Wikipedia page does a fine job of explaining the algorithms.