algorithm - 尝试理解 Min-Max Heap 的 delete-min

Question

我想了解min-max堆删除的过程是如何工作的，我已经搜索了它的伪代码但一无所获，而且我似乎不能在这里询问伪代码。所以这是我的问题

谁能展示“删除最小元素 7”的逻辑，至少让我知道伪代码“感觉如何”？

---

编辑:如果人们认为我什么都没尝试，这是另一张幻灯片:

1. [1.1]我不明白:

   (4-th line): ... and then reinsert into the min-max heap.

   这里的“reinsert”是调用原来的插入过程吗？或者它只是指它后面的案例？

   [1.2]

   (8-th line): The smallest key in the min-max heap is one of the children or grandchildren of the root.

   我不确定“孙子”是否递归地包括他们的孙子。

   幻灯片:

---

我能理解插入时使用的“VerifyMax”程序，不确定删除时是否会使用此程序...:

Answer 1

该算法“感觉像”普通最小堆的 DeleteMin 过程(或最大堆的 DeleteMax 过程):

1. 用堆中的最后一个元素替换当前的最小值(即堆中的第一个元素)。
2. 将堆的大小减一。
3. 对第一个元素使用 TrickleDown 过程以恢复堆属性。

TrickleDown 稍微复杂一些，但并不复杂:您需要检查最小和最大关系。通常这是通过检查 trickled 元素的子元素和孙元素来完成的。