algorithm - d-堆删除算法

Question

Binary heaps are so simple that they are almost always used when priority queues are needed. A simple generalization is a d-heap, which is exactly like a binary heap except that all nodes have d children (thus, a binary heap is a 2-heap).

Notice that a d-heap is much more shallow than a binary heap, improving the running time of inserts to O(log( base(d)n)). However, the delete_min operation is more expensive, because even though the tree is shallower, the minimum of d children must be found, which takes d - 1 comparisons using a standard algorithm. This raises the time for this operation to O(d logdn). If d is a constant, both running times are, of course, O(log n).

我的问题是对于 d 个 child ，我们应该进行 d 次比较，作者如何使用标准算法得出 d-1 次比较的结论。

谢谢!

Answer 1

你比 child 少了一个比较。

例如两个 child a1和a2您只比较一次 a1<=>a2找到较小的那个。

三个 child a1 , a2 , a3您比较一次以找到 a1 中较小的一个和a2第二次将较小的与 a3 进行比较.

通过归纳，您会发现对于每个额外的子项，您都需要进行额外的比较，将先前列表的最小值与新添加的子项进行比较。

因此，一般来说 d您需要的 child d-1比较以找到最小值。