I’m looking at the Heap chapter’s implementation for siftDown:
mutating func siftDown(from index: Int) {
var parent = index // 1
while true { // 2
let left = leftChildIndex(ofParentAt: parent) // 3
let right = rightChildIndex(ofParentAt: parent)
var candidate = parent // 4
if left < count && sort(elements[left], elements[candidate]) {
candidate = left // 5
}
if right < count && sort(elements[right], elements[candidate]) {
candidate = right // 6
}
if candidate == parent {
return // 7
}
elements.swapAt(parent, candidate) // 8
parent = candidate
}
}
The explanations for step 5 and 6 are:
- If there is a left child, and it has a higher priority than its parent, make it the candidate.
- If there is a right child, and it has an even greater priority, it will become the candidate instead.
However, if we only want to select the right child if it has an “even greater priority”, shouldn’t the comparison be sort(elements[right], elements[left]), and not sort(elements[right], elements[candidate])?