Quick Facts
- Complete Binary Tree
- Either a Min-Heap or Max-Heap
- Self Balancing
- Two most important operations are Insertion and the Extraction of highest priority element.
- The node at the top of the Heap has the greatest priority, the same is true for every node recursively moving down the tree structure.
- Moving down the tree, each level has twice as many nodes as the previous level.
- Min-Heap is synonymous with Priority Queue
- HeapSort uses a Max-Heap
- An Array is a great data structure for storing nodes in a Heap.
- Building helper functions greatly assists in calculations of indices, swapping node positions, and more.
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
public struct Heap<Element> { | |
var elements: [Element] | |
var priorityFunction: (Element, Element) -> Bool | |
init(elements: [Element] = [], priorityFunction: @escaping (Element, Element) -> Bool) { | |
self.elements = elements | |
self.priorityFunction = priorityFunction | |
buildHeap() | |
} | |
mutating func buildHeap() { | |
for index in (0 ..< count / 2).reversed() { | |
trickleDown(at: index) | |
} | |
} | |
var isEmpty: Bool { | |
return elements.isEmpty | |
} | |
var count: Int { | |
return elements.count | |
} | |
func peek() -> Element? { | |
return elements.first | |
} | |
func isRoot(_ index: Int) -> Bool { | |
return index == 0 | |
} | |
func leftChildIndex(of index: Int) -> Int { | |
return (2 * index) + 1 | |
} | |
func rightChildIndex(of index: Int) -> Int { | |
return (2 * index) + 2 | |
} | |
func parentIndex(of index: Int) -> Int { | |
return (index - 1) / 2 | |
} | |
func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool { | |
return priorityFunction(elements[firstIndex], elements[secondIndex]) | |
} | |
func highestPriority(of parentIndex: Int, and childIndex: Int) -> Int { | |
guard childIndex < count, isHigherPriority(at: childIndex, than: parentIndex) | |
else { return parentIndex } | |
return childIndex | |
} | |
func hightestPriority(at parentIndex: Int) -> Int { | |
return highestPriority(of: highestPriority(of: parentIndex, and: leftChildIndex(of: parentIndex)), and: rightChildIndex(of: parentIndex)) | |
} | |
mutating func swapElement(at firstIndex: Int, with secondIndex: Int) { | |
guard firstIndex != secondIndex | |
else { return } | |
let firstIndex = firstIndex | |
let secondIndex = secondIndex | |
elements.swapAt(firstIndex, secondIndex) | |
} | |
mutating func bubbleUp(at index: Int) { | |
guard !isRoot(index), isHigherPriority(at: index, than: parentIndex(of: index)) | |
else { return } | |
swapElement(at: index, with: parentIndex(of: index)) | |
bubbleUp(at: parentIndex(of: index)) | |
} | |
mutating func trickleDown(at index: Int) { | |
let childIndex = hightestPriority(at: index) | |
if index == childIndex { | |
return | |
} | |
swapElement(at: index, with: childIndex) | |
trickleDown(at: childIndex) | |
} | |
mutating func insert(_ element: Element) { | |
elements += [element] | |
bubbleUp(at: count - 1) | |
} | |
mutating func extract() -> Element? { | |
guard !isEmpty | |
else { return nil } | |
swapElement(at: 0, with: count - 1) | |
let element = elements.removeLast() | |
if !isEmpty { | |
trickleDown(at: 0) | |
} | |
return element | |
} | |
} |