d-heap删除算法

Question

二进制堆非常简单，几乎总是在需要优先级队列时使用它们。简单的泛化是一个d堆，其中 完全像二进制堆，但所有节点都有d个子 （因此，二进制堆是2堆）。

请注意，d-heap比二进制堆浅得多， 将插入的运行时间提高到O（log（base（d）n））。然而， delete_min操作更加昂贵，因为即使 树较浅，也必须找到最小d个子项，其中 使用标准算法进行d-1比较。这会将此操作的 时间提高到O（d logdn）。如果d是常数，那么 的运行时间当然是O（log n）。

我的问题是对于孩子，我们应该有比较，作者如何得出结论，使用标准算法的d-1比较。

谢谢！

Answer 1

你有一个比儿童少的比较。

E.g.对于两个孩子a1和a2你只比较一次a1<=>a2找到较小的一个。

对于三个孩子a1，a2，a3你比较一旦找到a1和a2较小，第二次以比较小的一个a3。

通过归纳可以看出，对于每个额外的孩子，您需要进行额外的比较，将以前列表的最小值与新添加的孩子进行比较。

因此，一般对于d孩子，您需要d-1比较来找到最小值。