Skip to content

Instantly share code, notes, and snippets.

@JCSooHwanCho
Created September 12, 2020 14:20
Show Gist options
  • Save JCSooHwanCho/a3f070c2160bb8c0047a5ddbb831f78e to your computer and use it in GitHub Desktop.
Save JCSooHwanCho/a3f070c2160bb8c0047a5ddbb831f78e to your computer and use it in GitHub Desktop.
swift로 간단하게 구현한 힙
public struct Heap<T> {
var nodes: [T] = []
let comparer: (T,T) -> Bool
var isEmpty: Bool {
return nodes.isEmpty
}
init(comparer: @escaping (T,T) -> Bool) {
self.comparer = comparer
}
func peek() -> T? {
return nodes.first
}
mutating func insert(_ element: T) {
var index = nodes.count
nodes.append(element)
while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) {
nodes.swapAt(index, (index-1)/2)
index = (index-1)/2
}
}
mutating func delete() -> T? {
guard !nodes.isEmpty else {
return nil
}
if nodes.count == 1 {
return nodes.removeFirst()
}
let result = nodes.first
nodes.swapAt(0, nodes.count-1)
_ = nodes.popLast()
var index = 0
while index < nodes.count {
let left = index * 2 + 1
let right = left + 1
if right < nodes.count {
if comparer(nodes[left], nodes[right]),
!comparer(nodes[right], nodes[index]) {
nodes.swapAt(right, index)
index = right
} else if !comparer(nodes[left], nodes[index]){
nodes.swapAt(left, index)
index = left
} else {
break
}
} else if left < nodes.count {
if !comparer(nodes[left], nodes[index]) {
nodes.swapAt(left, index)
index = left
} else {
break
}
} else {
break
}
}
return result
}
}
extension Heap where T: Comparable {
init() {
self.init(comparer: <)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment