最小-最大堆对于实现双端优先级队列非常有用，因为它的find-min和find-max操作时间是不变的。我们也可以在O(log2 n)时间内检索最小和最大堆中的最小和最大元素。然而，有时候，我们也可能想要删除最小最大值堆中的任何节点，这可以在O(log2 n)中完成，根据介绍最小最大值堆的论文:
…
该结构也可以推广为在常数时间内支持操作
Find(k)(确定结构中第k个最小值)和在对数时间内支持操作Delete(k)(删除结构中第k个最小值)，对于k的任何固定值(或值集)…
如何删除最小-最大堆上的第k个元素?
我不认为自己是算法和数据结构领域的"专家"，但我确实对二进制堆有详细的了解，包括最小-最大堆。例如，请参阅我关于二进制堆的博客系列，从http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/开始。我有一个最小-最大实现，我会在某个时候写出来。
你对这个问题的解决方案是正确的:当你删除一个任意节点时，你确实需要向上或向下过滤来重新调整堆。
在最小最大堆中删除任意节点与在最大堆或最小堆中删除相同的操作没有本质区别。例如，考虑删除最小堆中的任意节点。从min-heap开始:
0
4 1
5 6 2 3
现在，如果你删除节点5，你有:
0
4 1
6 2 3
取堆中的最后一个节点3，并将其放在5所在的位置:
0
4 1
3 6 2
在这种情况下，你不需要向下筛选，因为它已经是一个叶子，但它不合适，因为它比它的父结点小。你必须把它鼓起来才能得到:
0
3 1
4 6 2
同样的规则也适用于最小-最大堆。您将用堆中的最后一项替换要删除的元素，并减少计数。然后，你必须检查它是否需要起泡或过滤。唯一棘手的部分是，逻辑是不同的，取决于项目是在最小水平还是最大水平。
在您的示例中，第一个操作(用31替换55)产生的堆无效，因为31小于54。所以你必须把它放到堆中。
另一件事:删除任意节点确实是一个log2(n)操作。然而，查找要删除的节点是一个O(n)操作，除非您有一些其他数据结构来跟踪节点在堆中的位置。因此，一般来说，移除任意节点被认为是O(n)。
是什么导致我开发这个解决方案(我不是100%确定是正确的)的事实是，我实际上已经找到了一个解决方案来删除最小最大堆中的任何节点，但这是错误的。
错误的解决方案可以在这里(用c++实现)和这里(用Python实现)找到。我将介绍刚才提到的错误的Python解决方案，它对每个人来说都更容易理解:
解决方案如下:
def DeleteAt(self, position):
"""delete given position"""
self.heap[position] = self.heap[-1]
del(self.heap[-1])
self.TrickleDown(position)
level 0 10
level 1 92 56
level 2 41 54 23 11
level 3 69 51 55 65 37 31
据我所知，这是一个有效的最小最大堆。现在，假设我们要删除元素55，在基于0的数组中，它应该位于索引9处(如果我计数正确的话)。
上面的解决方案是简单地将数组中的最后一个元素(在本例中为31)放在位置9:
level 0 10
level 1 92 56
level 2 41 54 23 11
level 3 69 51 31 65 37 55
将删除数组的最后一个元素(现在是55)，生成的最小-最大堆看起来像这样:
level 0 10
level 1 92 56
level 2 41 54 23 11
level 3 69 51 31 65 37
，最后它会从position"滴下"(即现在我们有数字31)。
"tricle-down"将检查我们是否处于偶数(或min)或奇数(或max)级别:我们处于奇数(3)级别，因此"trickle-down"将从31开始调用"trickle-down-max"，但由于31没有子节点，它会停止(如果你不知道我在说什么，请查看上面的原始论文)。
但是如果你观察到这使得数据结构处于no的状态，更像是一个最小-最大堆，因为54是偶数级，因此应该小于它的后代，大于31，它的后代之一。
这让我认为我们不能只看position节点的子节点，但我们也需要从position向上检查，也许我们也需要使用"涓滴向上"。
在下面的推理中，设x是在删除要删除的元素之后，在执行任何修复操作之前，position处的元素。设p为它的父级(如果有的话)。
我的算法的想法就是这样，更具体地说，是基于以下事实:
如果
x位于奇数级别(如上面的示例)，并且我们将其与位于偶数级别的父p交换，这将不会从新的x的位置向下破坏最小-最大堆的任何规则/不变量。如果情况相反，同样的推理(我认为)可以做到，即
x最初处于偶数位置，它将大于其父节点。现在，如果你注意到，唯一可能需要修复的是，如果
x与它的父节点交换，它现在处于偶数(分别为奇数)位置，我们可能需要检查它是否比之前的偶数(分别为奇数)级别的节点更小(和更大)。
这当然不是我的全部解决方案，当然我也想检查x的前父节点，即p，是否在正确的位置。
如果
p在与x交换后处于奇数(分别为偶数)水平，这意味着它可能比它的任何后代都小(分别为大)，因为它之前处于偶数(分别为奇数)水平。所以，我认为我们需要一个"滴入式"。关于
p在其祖先方面处于正确位置的事实，我认为推理将与上面的相似(但我不是100%确定)。
把这些放在一起，我想出了解决方案:
function DELETE(H, i):
// H is the min-max heap array
// i is the index of the node we want to delete
// I assume, for simplicity,
// it's not out of the bounds of the array
if i is the last index of H:
remove and return H[i]
else:
l = get_last_index_of(H)
swap(H, i, l)
d = delete(H, l)
// d is the element we wanted to remove initially
// and was initially at position i
// So, at index i we now have what was the last element of H
push_up(H, i)
push_down(H, i)
return d
这似乎是根据我所做的最小最大堆的实现来工作的，你可以在这里找到。
还请注意，解决方案运行在O(log2 n)时间内，因为我们只是调用"俯卧"one_answers"俯卧"，它们按此顺序运行。