A Note on Bottom-Up Skew Heaps
Douglas W. Jones · SIAM Journal on Computing · 1987
In testing Sleator and Tarjan’s skew heap implementations of priority queues, a problem with the bottom-up variant was found. The original definition of skew heaps includes the assumption that the keys of items in the heap are disjoint. When this is not true, the delete min operation on bottom-up skew heaps will occasionally discard items from the heap. Modified versions of the delete min algorithm are presented which do not require this assumption.