Skip to content

Instantly share code, notes, and snippets.

@nmn nmn/HaskellySkewHeap.swift
Last active Dec 22, 2016

Embed
What would you like to do?
Swift Skew Heap
// 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))
}
}
/// 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
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.