diff options
| -rw-r--r-- | src/libcollections/binary_heap.rs | 15 |
1 files changed, 8 insertions, 7 deletions
diff --git a/src/libcollections/binary_heap.rs b/src/libcollections/binary_heap.rs index 30fc22e400a..bdf5f5b2a83 100644 --- a/src/libcollections/binary_heap.rs +++ b/src/libcollections/binary_heap.rs @@ -521,29 +521,30 @@ impl<T: Ord> BinaryHeap<T> { while hole.pos() > start { let parent = (hole.pos() - 1) / 2; - if hole.removed() <= hole.get(parent) { break } + if hole.element() <= hole.get(parent) { break; } hole.move_to(parent); } } } - fn sift_down_range(&mut self, mut pos: usize, end: usize) { - let start = pos; + /// Take an element at `pos` and move it down the heap, + /// while its children are larger. + fn sift_down_range(&mut self, pos: usize, end: usize) { unsafe { let mut hole = Hole::new(&mut self.data, pos); let mut child = 2 * pos + 1; while child < end { let right = child + 1; + // compare with the greater of the two children if right < end && !(hole.get(child) > hole.get(right)) { child = right; } + // if we are already in order, stop. + if hole.element() >= hole.get(child) { break; } hole.move_to(child); child = 2 * hole.pos() + 1; } - - pos = hole.pos; } - self.sift_up(start, pos); } fn sift_down(&mut self, pos: usize) { @@ -605,7 +606,7 @@ impl<'a, T> Hole<'a, T> { /// Return a reference to the element removed #[inline(always)] - fn removed(&self) -> &T { + fn element(&self) -> &T { self.elt.as_ref().unwrap() } |