Skip to content

Instantly share code, notes, and snippets.

@jolasjoe
Created April 1, 2024 03:36
Show Gist options
  • Save jolasjoe/8b167208cae767ac0f9116570aadd0c0 to your computer and use it in GitHub Desktop.
Save jolasjoe/8b167208cae767ac0f9116570aadd0c0 to your computer and use it in GitHub Desktop.
Simple implementation of Heap in swift
struct Heap<E> {
var storage: [E]
var compare: (E, E) -> Bool
var count: Int { storage.count }
init(storage: [E], compare: @escaping (E, E) -> Bool) {
self.storage = storage
self.compare = compare
for i in (0...((count - 1)/2)).reversed() {
siftDown(i)
}
}
func peek() -> E? {
guard storage.count > 0 else { return nil }
return storage[0]
}
mutating func insert(_ val: E) {
storage.append(val)
siftUp(count - 1)
}
mutating func pop() -> E? {
if storage.count == 0 { return nil }
if count == 1 { return storage.removeLast() }
storage.swapAt(0, count - 1)
var result = storage.removeLast()
siftDown(0)
return result
}
mutating func siftDown(_ i: Int) {
guard i < count else { return }
var left = left(i)
var right = right(i)
var swap = i
if left < count, compare(storage[left], storage[swap]) {
swap = left
}
if right < count, compare(storage[right], storage[swap]) {
swap = right
}
if swap == i { return }
storage.swapAt(i, swap)
siftDown(swap)
}
mutating func siftUp(_ i: Int) {
guard i > 0 else { return }
var parent = parent(i)
if parent >= 0, compare(storage[i], storage[parent]) {
storage.swapAt(i, parent)
}
siftUp(parent)
}
func left(_ i: Int) -> Int { return 2 * i + 1 }
func right(_ i: Int) -> Int { return 2 * i + 2 }
func parent(_ i: Int) -> Int { return (i - 1) / 2 }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment