diff options
| -rw-r--r-- | library/alloc/src/collections/binary_heap.rs | 32 |
1 files changed, 19 insertions, 13 deletions
diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs index b67c72d7136..97ebc12175f 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap.rs @@ -495,7 +495,14 @@ impl<T: Ord> BinaryHeap<T> { let mut end = self.len(); while end > 1 { end -= 1; - self.data.swap(0, end); + // SAFETY: `end` goes from `self.len() - 1` to 1 (both included), + // so it's always a valid index to access. + // It is safe to access index 0 (i.e. `ptr`), because + // 1 <= end < self.len(), which means self.len() >= 2. + unsafe { + let ptr = self.data.as_mut_ptr(); + ptr::swap(ptr, ptr.add(end)); + } self.sift_down_range(0, end); } self.into_vec() @@ -531,19 +538,19 @@ impl<T: Ord> BinaryHeap<T> { unsafe { let mut hole = Hole::new(&mut self.data, pos); let mut child = 2 * pos + 1; - while child < end { - let right = child + 1; + while child < end - 1 { // compare with the greater of the two children - if right < end && hole.get(child) <= hole.get(right) { - child = right; - } + child += (hole.get(child) <= hole.get(child + 1)) as usize; // if we are already in order, stop. if hole.element() >= hole.get(child) { - break; + return; } hole.move_to(child); child = 2 * hole.pos() + 1; } + if child == end - 1 && hole.element() < hole.get(child) { + hole.move_to(child); + } } } @@ -563,15 +570,14 @@ impl<T: Ord> BinaryHeap<T> { 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; - } + while child < end - 1 { + child += (hole.get(child) <= hole.get(child + 1)) as usize; hole.move_to(child); child = 2 * hole.pos() + 1; } + if child == end - 1 { + hole.move_to(child); + } pos = hole.pos; } self.sift_up(start, pos); |