Skip to content

Instantly share code, notes, and snippets.

@GuanshanLiu
Created September 29, 2018 12:24
Show Gist options
  • Save GuanshanLiu/ce8bb930a797174c0161769023133c8e to your computer and use it in GitHub Desktop.
Save GuanshanLiu/ce8bb930a797174c0161769023133c8e to your computer and use it in GitHub Desktop.
/// Complexity: O(log n)
public mutating func remove() -> Element? {
guard !isEmpty else { return nil }
elements.swapAt(0, count - 1)
defer {
shiftDown(from: 0)
}
return elements.removeLast()
}
private mutating func shiftDown(from index: Int) {
var parent = index
while true {
let leftChild = leftChildIndex(forParentAt: parent)
let rightChild = rightChildIndex(forParentAt: parent)
var next = parent
if leftChild < count && sort(elements[leftChild], elements[next]) {
next = leftChild
}
if rightChild < count && sort(elements[rightChild], elements[next]) {
next = rightChild
}
if next == parent {
// No need to shift down any more
break
}
elements.swapAt(parent, next)
parent = next
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment