BinaryHeap: Use full sift down in .pop()

.sift_down can either choose to compare the element on the way down (and
place it during descent), or to sift down an element fully, then sift
back up to place it.

A previous PR changed .sift_down() to the former behavior, which is much
faster for relatively small heaps and for elements that are cheap to
compare.

A benchmarking run suggested that BinaryHeap::pop() suffers
improportionally from this, and that it should use the second strategy
instead. It's logical since .pop() brings last element from the
heapified vector into index 0, it's very likely that this element will
end up at the bottom again.

1 files changed, 26 insertions, 1 deletions

diff --git a/src/libcollections/binary_heap.rs b/src/libcollections/binary_heap.rs
index effd4ebb316..bd329949618 100644
--- a/src/libcollections/binary_heap.rs
+++ b/src/libcollections/binary_heap.rs
@@ -354,7 +354,7 @@ impl<T: Ord> BinaryHeap<T> {
         self.data.pop().map(|mut item| {
             if !self.is_empty() {
                 swap(&mut item, &mut self.data[0]);
-                self.sift_down(0);
+                self.sift_down_to_bottom(0);
             }
             item
         })
@@ -545,6 +545,31 @@ impl<T: Ord> BinaryHeap<T> {
         self.sift_down_range(pos, len);
     }
 
+    /// Take an element at `pos` and move it all the way down the heap,
+    /// then sift it up to its position.
+    ///
+    /// Note: This is faster when the element is known to be large / should
+    /// be closer to the bottom.
+    fn sift_down_to_bottom(&mut self, mut pos: usize) {
+        let end = self.len();
+        let start = pos;
+        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;
+                }
+                hole.move_to(child);
+                child = 2 * hole.pos() + 1;
+            }
+            pos = hole.pos;
+        }
+        self.sift_up(start, pos);
+    }
+
     /// Returns the length of the binary heap.
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn len(&self) -> usize {