What is a Heap
A Heap is a tree with the requirement that the value of a node must be greater or smaller than the value of the children.
It is very useful when we what to implement priority queues and is being used in many common algorithms such as Dijkstra, Prims and many others.
Complexity
Find: O(1)
Search: O(n)
Insert: O(logn)
Remove: O(logn)
Swift Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
class Heap<T: Equatable> { private var nodes: [T] = [] private let compare: (T, T) -> Bool public init(_ compare: @escaping (T, T) -> Bool) { self.compare = compare } public var isEmpty: Bool { nodes.isEmpty } public var count: Int { nodes.count } public var peek: T? { nodes.first } public func insert(node: T) { nodes.append(node) heapifyUp(nodes.count - 1) } public func remove(node: T) -> T? { guard let first = nodes.first else { return nil } guard nodes.count > 1 else { return nodes.removeLast() } nodes[0] = nodes.removeLast() heapifyDown(0) return first } private func heapifyUp(_ index: Int) { var currentIndex = index while currentIndex > 0 { let parentIndex = parentIndex(ofIndex: currentIndex) if compare(nodes[currentIndex], nodes[parentIndex]) { nodes.swapAt(currentIndex, parentIndex) currentIndex = parentIndex } else { break } } } private func heapifyDown(_ index: Int) { var currentIndex = index var firstChildIndex = currentIndex while currentIndex < nodes.count { let leftChildIndex = leftChildIndex(ofIndex: currentIndex) let rightChildIndex = rightChildIndex(ofIndex: currentIndex) if leftChildIndex < nodes.count && compare(nodes[leftChildIndex], nodes[firstChildIndex]) { firstChildIndex = leftChildIndex } if rightChildIndex < nodes.count && compare(nodes[rightChildIndex], nodes[firstChildIndex]) { firstChildIndex = rightChildIndex } if currentIndex != firstChildIndex { nodes.swapAt(currentIndex, firstChildIndex) currentIndex = firstChildIndex } else { break } } } } extension Heap { func parentIndex(ofIndex i: Int) -> Int { return (i - 1) / 2 } func leftChildIndex(ofIndex i: Int) -> Int { return 2 * i + 1 } func rightChildIndex(ofIndex i: Int) -> Int { return 2 * i + 2 } } |
Github Link:
https://github.com/Fragki/Heap
