d-heaps deletion algorithm

Binary heaps are so 开发者_如何学Pythonsimple 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).

My question is for d childeren we should have d comparisions, how author concluded that d-1 comparisions using a standard algorithm.

Thanks!

---

You have one comparison less than children.

E.g. for two children a1 and a2 you compare only once a1<=>a2 to find the smaller one.

For three children a1, a2, a3 you compare once to find the smaller of a1 and a2 and a second time to compare the smaller one to a3.

By induction you see that for each additional child you need an additional comparison, comparing the minimum of the previous list with the newly added child.

Thus, in general for d children you need d-1 comparisons to find the minimum.