Swift Skew Heap

HaskellySkewHeap.swift

// 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))
    }
}

SwiftSkewHeap.swift

/// reference: 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>)

    static func create(_ a: T) -> SkewHeap<T> {
        return .Node(a, .Empty, .Empty)
    }

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

    func insert(_ x: T) -> SkewHeap<T> {
        return SkewHeap.create(x).union(self)
    }

    mutating func extractMin() -> T? {
        switch self {
        case .Empty:
            return nil
        case let .Node(x, l, r):
            self = l.union(r)
            return x
        }
    }
}