make the right child its own subtree.) This will result in a set of trees in which the root either only has a left child or no children at all. Sort the subtrees in ascending order based on the value of the root node of each subtree. While there are still multiple subtrees, iteratively recombine the last two (from right to left). If the root of the second-to-last subtree has a left child, swap it to be the right child. Link the root of the last subtree as the left child of the second-to-last subtree. Adding values Adding a value to a skew heap is like merging a tree with one node together with the original tree. Removing values Removing the first value in a heap can be accomplished by removing the root and merging its child subtrees. Implementation In many functional languages, skew heaps become extremely simple to implement. Here is a complete sample implementation in Haskell. data SkewHeap a = Empty | Node a (SkewHeap a) (SkewHeap a) singleton :: Ord a => a -> SkewHeap a singleton x = Node x Empty Empty union :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a Empty `union` t2 = t2 t1 `union` Empty = t1 t1@(Node x1 l1 r1) `union` t2@(Node x2 l2 r2) | x1 <= x2 = Node x1 (t2 `union` r1) l1 | otherwise = Node x2 (t1 `union` r2) l2 insert :: Ord a => a -> SkewHeap a -> SkewHeap a insert x heap = singleton x `union` heap extractMin :: Ord a => SkewHeap a -> Maybe (a, SkewHeap a) extractMin Empty = Nothing extractMin (Node x l r) = Just (x, l `union` r) References External links Lecture notes, Skew Heaps, York University Animations comparing leftist heaps and skew heaps, York University Javascript skew heap simulation, University of San Francisco Java applet for simulating heaps, Kansas State University Binary trees Heaps (data structures)