heap.swift

enum Heap<Key: Comparable> {
    case empty(key: Key)
    indirect case halfFull(key: Key, left: Heap<Key>)
    indirect case full(key: Key, left: Heap<Key>, right: Heap<Key>)
}

extension Heap {
    var isFull: Bool {
        if case .full(key: _, left: _, right: _) = self {
            return true
        }
        return false
    }

    var key: Key {
        get {
            switch self {
            case .empty(key: let key): return key
            case .halfFull(key: let key, left: _): return key
            case .full(key: let key, left: _, right: _) : return key
            }
        } set {
            switch self {
            case .empty(key: _): self = .empty(key: newValue)
            case .halfFull(key: _, left: let left): self = .halfFull(key: newValue, left: left)
            case .full(key: _, left: let left, right: let right): self = .full(key: newValue, left: left, right: right)
            }
        }
    }

    var children: [Heap<Key>] {
        switch self {
        case .empty(key: _): return []
        case .halfFull(key: _, left: let left): return [left]
        case .full(key: _, left: let left, right: let right): return [left, right]
        }
    }
}

extension Heap {
    func levelsFull() -> Int {
        if self.isFull {
            return 1 + self.children.map { $0.levelsFull() }.reduce(0, combine: +)
        }
        return 0
    }

    mutating func insert(key: Key, comparator: (Key, Key) -> Bool) {
        insert(.empty(key: key), comparator: comparator)
    }

    mutating func insert(node: Heap<Key>, comparator: (Key, Key) -> Bool) {
        var node = node
        if comparator(node.key, self.key) {
            swap(&self.key, &node.key)
        }

        switch self {
        case let .empty(key: key):
            self = .halfFull(key: key, left: node)
        case let .halfFull(key: key, left: left):
            self = .full(key: key, left: left, right: node)
        case .full(key: _, left: var left, right: var right):

            if right.levelsFull() < left.levelsFull() {
                right.insert(node, comparator: >)
            } else {
                left.insert(node, comparator: >)
            }

            self = .full(key: key, left: left, right: right)
        }
    }
}

extension Heap {
    var description: String {
        return pretty(depth: 0)
    }

    func pretty(depth depth: Int) -> String {
        let padding = (0..<depth).map { _ in "\t" }.reduce("", combine: +)

        let key = "- \(self.key)"
        let children = self.children.map { $0.pretty(depth: depth + 1) }.reduce("", combine: +)
        
        return padding + key + "\n" + children
    }
}

var test1: Heap = .empty(key: 4)

test1.insert(6, comparator: >)
test1.insert(3, comparator: >)
test1.insert(8, comparator: >)
test1.insert(2, comparator: >)
test1.insert(10, comparator: >)

print(test1.description)

// output:
// - 10
//     - 6
//         - 4
//         - 2
//     - 8
//         - 3