我有一种情况，我想从堆中删除一个随机节点，我有什么选择？我知道我们可以轻松删除堆的最后一个节点和第一个节点。但是，如果我们说删除最后一个节点，那么我不确定是否正确定义了从堆中删除随机节点的行为。
例如
_______________________
|X|12|13|14|18|20|21|22|
------------------------
所以在这种情况下，我可以删除节点 12 和 22，这是已定义的，但是我可以删除一个随机节点，例如 13，并且仍然以某种方式维护堆的完整树属性（以及其他属性）吗？
我假设您正在描述一个在数组中维护的二进制堆，具有不变的 thatA[N] <= A[N*2]和A[N] <= A[N*2 + 1]（最小堆）。
如果是，那么删除的方法很简单：用最后一个元素替换已删除的元素，并执行筛选以确保它最终出现在正确的位置。当然，减少保存堆中条目总数的变量。
顺便说一句，如果您正在处理堆示例，我发现使用没有总排序的示例会更好。堆的定义中没有任何内容需要 (eg) A[3] <= A[5]，如果您的示例具有这样的顺序，很容易被误导。
我不认为可以从堆中删除随机元素。让我们举这个例子（遵循相同的约定）：
3, 10, 4, 15, 20, 6, 5.
现在如果我删除元素 15，堆变成：3, 10, 4, 5, 20, 6
这使得堆不一致，因为5它是 的子级10。
我认为随机删除不起作用的原因是因为您可以替换堆中的内部节点（而不是根或叶），因此有两条路径（父母和孩子）到heapify（与1路径相比pop()或insert()）。如果我在这里遗漏了什么，请告诉我。