是否可以从堆中删除随机节点？
我有一种情况，我想从堆中删除一个随机节点，我有什么选择？我知道我们可以轻松删除堆的最后一个节点和第一个节点。但是，如果我们说删除最后一个节点，那么我不确定是否正确定义了从堆中删除随机节点的行为。
例如
_______________________
|X|12|13|14|18|20|21|22|
------------------------
，在这种情况下，我可以删除节点 12 和 22，这是已定义的，但是我可以删除一个随机节点（例如 13），并且仍然以某种方式维护堆的完整树属性（以及其他属性）吗？
I have a situation where I want to delete a random node from the heap, what choices do I have? I know we can easily delete the last node and the first node of the heap. However if we say delete the last node, then I am not sure if the behavior is correctly defined for deleting a random node from the heap.
e.g.
_______________________
|X|12|13|14|18|20|21|22|
------------------------
So in this case I can delete the node 12 and 22, this is defined, but can I for example delete a random node, e.g. say 13, and still somehow maintain the complete tree property of the heap (along with other properties)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我假设您正在描述一个在数组中维护的二进制堆，其不变量为
A[N] <= A[N*2]和A[N] < ;= A[N*2 + 1]（最小堆）。如果是，那么删除的方法很简单：用最后一个元素替换已删除的元素，并执行筛选以确保它最终位于正确的位置。当然，还要减少保存堆中条目总数的变量。
顺便说一句，如果您正在处理堆示例，我发现最好使用没有总排序的示例。堆的定义中没有任何内容需要（例如）
A[3] <= A[5]，并且如果您的示例具有这样的顺序，则很容易被误导。I'm assuming that you're describing a binary heap maintained in an array, with the invariant that
A[N] <= A[N*2]andA[N] <= A[N*2 + 1](a min-heap).If yes, then the approach to deletion is straightforward: replace the deleted element with the last element, and perform a sift-down to ensure that it ends up in the proper place. And, of course, decrement the variable that holds the total number of entries in the heap.
Incidentally, if you're working through heap examples, I find it better to use examples that do not have a total ordering. There's nothing in the definition of a heap that requires (eg)
A[3] <= A[5], and it's easy to get misled if your examples have such an ordering.我不认为可以从堆中删除随机元素。让我们举个例子（遵循相同的约定）：
3, 10, 4, 15, 20, 6, 5.现在，如果我删除元素 15，堆将变为：
3, 10, 4 , 5, 20, 6这使得堆不一致，因为
5是10的子级。我认为随机删除不起作用的原因是因为您可以替换堆中的内部节点（而不是根或叶子），因此有两条路径（父级和子级）到
heapify（与pop()或insert()情况下的1路径相比）。如果我在这里遗漏了什么，请告诉我。
I don't this think it is possible to remove random element from a heap. Let's take this example (following same convention):
3, 10, 4, 15, 20, 6, 5.Now if I delete element 15, the heap becomes:
3, 10, 4, 5, 20, 6This makes heap inconsistent because of
5being child of10.The reason I think random deletion won't work is because you may substitute an inside node (instead of root or a leaf) in the heap, and thus there are two paths (parents and children) to
heapify(as compared to1path in case ofpop()orinsert()).Please let me know in case I am missing something here.