// https://en.wikipedia.org/wiki/Skew_heap#Implementation
import Foundation

indirect enum SkewHeap<T> where T: Equatable, T: Comparable {
    case Empty
    case Node(T, SkewHeap<T>, SkewHeap<T>)
}

func singleton<T>(_ a: T) -> SkewHeap<T> where T: Equatable, T: Comparable {
    return .Node(a, .Empty, .Empty)
}

func union<T>(_ a: SkewHeap<T>, _ b: SkewHeap<T>) -> SkewHeap<T> where T: Equatable, T: Comparable {
    switch (a, b) {
    case (.Empty, _):
        return b
    case (_, .Empty):
        return a
    case let (.Node(x1, l1, r1), .Node(x2, l2, r2)):
        if (x1 <= x2) {
            return .Node(x1, union(b, r1), l1)
        } else {
            return .Node(x2, union(a, r2), l2)
        }
    default:
        return .Empty
    }
}

func insert<T>(_ x: T, _ heap: SkewHeap<T>) -> SkewHeap<T> where T: Equatable, T: Comparable {
    return union(singleton(x), heap)
}

func extractMin<T>(_ heap: SkewHeap<T>) -> (T, SkewHeap<T>)? where T: Equatable, T: Comparable {
    switch heap {
    case .Empty:
        return nil
    case let .Node(x, l, r):
        return (x, union(l, r))
    }
}