Skew heap

In contrast with binary heaps, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic.

However, amortized complexity analysis can be used to demonstrate that all operations on a skew heap can be done in O(log n).

denoting the golden ratio, the exact amortized complexity is known to be logφ n (approximately 1.44 log2 n).

Alternatively, there is a non-recursive approach which is more wordy, and does require some sorting at the outset.

In many functional languages, skew heaps become extremely simple to implement.