A skew heap is a self-adjusting node-based data structure where push, pop and merging of two heaps may all be performed in O(ln(n)) amortized time. A merge is perfomed using a simple routine: merging two skew heaps A and B, if the top of A is less than or equal to the top of B, A becomes the skew heap, its children are swapped and B is merged with the left sub-heap of the root of A. If the left sub-heap is empty, B is assigned to the left sub-heap of A.

The primary operation of skew heaps is a merge operation of two skew heaps. Once this is defined, we may define push and pop in terms of merge operations:

• Pushing a single object onto a skew heap is the same as merging the exisiting skew heap with a skew heap comprised of a single node, and
• Popping the minimum element from a skew heap is equivalent to removing the root node and then merging the right subtree with the skew subtree.