Skip to content

Instantly share code, notes, and snippets.

@sooop
Last active Jun 24, 2016
Embed
What would you like to do?
Heap ADT implemented in Swift3
//: heap implemented in Swift3
public struct Heap<T> {
public typealias Comparator = (T, T) -> Bool
private var elements: [T] = []
private var __isOrderedBefore: Comparator
public var peak: T? { return elements.first }
public var count: Int { return elements.count }
public var isEmpty: Bool { return elements.isEmpty }
public init(comparator: Comparator) {
__isOrderedBefore = comparator
}
public init(array:[T], comparator: Comparator) {
__isOrderedBefore = comparator
buildHeap(from:array)
}
@inline(__always) private func parent(of i: Int) -> Int? {
guard i > 0 else { return nil }
return (i - 1) / 2
}
@inline(__always) private func leftChild(of i: Int) -> Int? {
if case let c = (i * 2) + 1 where c < elements.count { return c }
return nil
}
@inline(__always) private func rightChild(of i: Int) -> Int? {
if case let c = (i * 2) + 2 where c < elements.count { return c }
return nil
}
@inline(__always) private mutating func swapElement(_ a: Int, _ b: Int) {
(elements[a], elements[b]) = (elements[b], elements[a])
}
@inline(__always) private func isOrderedBefore(_ a: Int, _ b: Int) -> Bool {
return __isOrderedBefore(elements[a], elements[b])
}
private mutating func shiftUp(at _i: Int) {
var i = _i
while let p = parent(of: i) where isOrderedBefore(i, p) {
swapElement(i, p)
i = p
}
}
private mutating func add(_ e: T) {
elements.append(e)
shiftUp(at:elements.count - 1)
}
mutating func buildHeap(from arr: [T]) { arr.forEach{ add($0) } }
private func availableChild(at i: Int) -> Int? {
guard let l = leftChild(of: i) else { return nil }
if let r = rightChild(of: i) {
let x = isOrderedBefore(l, r) ? l : r
return isOrderedBefore(x, i) ? x : nil
}
return isOrderedBefore(l, i) ? l : nil
}
private mutating func shiftDown(at _i: Int) {
var i = _i
while case let c? = availableChild(at:i) {
swapElement(i, c)
i = c
}
}
public mutating func remove() -> T? {
guard !isEmpty else { return nil }
let result = elements[0]
let r = elements.removeLast()
if !elements.isEmpty {
elements[0] = r
shiftDown(at:0)
}
return result
}
}
var h = Heap<Int>(comparator:<)
for i in [8, 4, 36, 25, 6, 10, 12] {
h.add(i)
}
while let x = h.remove() {
print(x)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment