Treap

data Treap key priority = Treap key priority (Treap key priority) (Treap key priority) | EmptyTreap
    deriving (Show, Read)

splitTreap EmptyTreap _ = (EmptyTreap, EmptyTreap)
splitTreap (Treap key priority left right) splitKey
    | splitKey < key = (fst leftSplit, Treap key priority (snd leftSplit) right)
    | otherwise = (Treap key priority left (snd rightSplit), fst rightSplit)
        where
            leftSplit = splitTreap left splitKey
            rightSplit = splitTreap right splitKey

mergeTreap EmptyTreap t = t
mergeTreap t EmptyTreap = t
mergeTreap t1@(Treap k1 p1 l1 r1) t2@(Treap k2 p2 l2 r2)
    | p1 < p2 = Treap k1 p1 l1 (mergeTreap r1 t2)
    | otherwise = Treap k2 p2 (mergeTreap t1 l2) r2

insertTreap EmptyTreap t = t
insertTreap t1@(Treap k1 p1 l1 r1) t2@(Treap k2 p2 l2 r2)
    | p2 < p1 = Treap k2 p2 (fst splitResult) (snd splitResult)
    | k2 < k1 = Treap k1 p1 (insertTreap l1 t2) r1
    | otherwise = Treap k1 p1 l1 (insertTreap r1 t2)
        where
            splitResult = splitTreap t1 k2

removeTreap EmptyTreap _ = EmptyTreap
removeTreap (Treap key priority left right) removeKey
    | key == removeKey = mergeTreap left right
    | removeKey < key = Treap key priority (removeTreap left removeKey) right
    | otherwise = Treap key priority left (removeTreap right removeKey)

findTreap EmptyTreap _ = Nothing
findTreap (Treap key priority left right) findKey
    | key == findKey = Just (key, priority)
    | findKey < key = findTreap left findKey
    | otherwise = findTreap right findKey

buildTreapSimple :: (Ord a, Ord b) => [(a, b)] -> Treap a b
buildTreapSimple = foldl (\x y -> insertTreap x (Treap (fst y) (snd y) EmptyTreap EmptyTreap)) EmptyTreap