About binomial queue performance

Question

Below text is from binomial queues article.

Although both leftist and skew heaps support merging, insertion, and delete_min all effectively in O(log n) time per operation, there is room for improvement because we know that binary heaps support insertion in constant average time per operation. Binomial queues support all three operations in O(log n) worst-case time per operation, but insertions take constant time on average.

In above text what does author mean by constant average time per operation? and how it is different from for binomial queues insertion takes constant time on average?

What is difference between constant average time per operation and constant time on average?

Answer 1

What is difference between constant average time per operation and constant time on average?

There is no difference. The author is contrasting leftist and skew heaps on the one hand, and binary heaps on the other, to show that binomial heaps have some of the advantages of binary heaps (expected O(1) insert) that leftist and skew heaps do not have (they only have amortized O(1) insert).