Editing Binomial heap (section)

=== Insert ===
'''Inserting''' a new element to a heap can be done by simply creating a new heap containing only this element and then merging it with the original heap. Because of the merge, a single insertion takes time <math>O(\log n)</math>. However, this can be sped up using a merge procedure that shortcuts the merge after it reaches a point where only one of the merged heaps has trees of larger order. With this speedup, across a series of <math>k</math> consecutive insertions, the total time for the insertions is <math>O(k+\log n)</math>. Another way of stating this is that (after logarithmic overhead for the first insertion in a sequence) each successive '''insert''' has an [[Amortized time|''amortized'' time]] of <math>O(1)</math> (i.e. constant) per insertion.<ref name="clrs" /><ref name="brown" />

A variant of the binomial heap, the [[skew binomial heap]], achieves constant worst case insertion time by using forests whose tree sizes are based on the [[skew binary number system]] rather than on the binary number system.<ref>{{citation
 | last1 = Brodal | first1 = Gerth Stølting
 | last2 = Okasaki | first2 = Chris
 | date = November 1996
 | doi = 10.1017/s095679680000201x
 | issue = 6
 | journal = Journal of Functional Programming
 | pages = 839–857
 | title = Optimal purely functional priority queues
 | volume = 6| doi-access = free
 }}</ref>