Skip to content

Instantly share code, notes, and snippets.

@GuanshanLiu
Last active September 29, 2018 12:22
Show Gist options
  • Save GuanshanLiu/02562dcb17839a86d7ba7db78e4c5db9 to your computer and use it in GitHub Desktop.
Save GuanshanLiu/02562dcb17839a86d7ba7db78e4c5db9 to your computer and use it in GitHub Desktop.
/// Complexity: O(log n)
public mutating func insert(_ element: Element) {
elements.append(element)
shiftUp(from: count - 1)
}
private mutating func shiftUp(from index: Int) {
var child = index
var parent = parentIndex(forChildAt: child)
while child > 0 && sort(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = parentIndex(forChildAt: child)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment