Created
April 1, 2024 03:36
-
-
Save jolasjoe/8b167208cae767ac0f9116570aadd0c0 to your computer and use it in GitHub Desktop.
Simple implementation of Heap in swift
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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