Skip to content

Instantly share code, notes, and snippets.

@Danappelxx
Last active March 29, 2016 19:04
Show Gist options
  • Save Danappelxx/75f4fe9e2dbed8cf4418 to your computer and use it in GitHub Desktop.
Save Danappelxx/75f4fe9e2dbed8cf4418 to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment